Source-linked AI summary
Almost Empty Monochromatic Triangles With Many Colors
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
TL;DR
The paper studies how the guaranteed interior-point count for monochromatic triangles behaves as the number of colors grows. It refines a recursive blocking argument to improve the upper-bound correction for sufficiently large c, while leaving the leading constant unchanged.
Problem
The paper asks how λ_3(c) behaves as the number of colors grows, following the study of almost empty monochromatic triangles in colored planar point sets.
Source: §1 · p. 2Method
The proof iterates a triangulation-and-blocking strategy, selecting a most frequent unused color at each step and allowing the number of recursive steps to grow with c.
Source: §1 · p. 2Results
For sufficiently large c, the upper-bound additive correction improves from -3 to order -sqrt(c log c).
Source: §1 · p. 2Takeaways & Limitations
The paper shows that the previously established lower bound is tight within the class of Horton sets.
Source: §1 · p. 3Theorem 1.1 improves the second-order term but does not change the upper bound's leading constant.
Source: §1 · p. 3
Abstract
from arXiv · showhide
Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $\lambda_3(c)$ be the least integer such that $\mathsf{M}_3(c,\lambda_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq \lambda_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$\lambda_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $\lambda_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $\lambda_3(c)$.
1 Introduction
The introduction presents an asymptotic improvement to the upper bound on λ3(c) and a matching lower-bound result for sufficiently large Horton sets. It outlines the refined recursive proof and notes that the leading asymptotic constant remains unchanged.
1 Introduction
- Prior work initiated the study of almost-empty monochromatic triangles after empty monochromatic triangles were shown not to exist for three or more colors; Cravioto-Lagos et al. improved the upper bound to c−3 for c≥4.The combined bounds determine λ3(c) for c≤5 and give linear bounds for c≥6.Source: §1 · p. 2
- For sufficiently large c, the upper bound on λ3(c) improves by an additive correction of order √(c log c).The paper describes this as an improvement over the fixed −3 correction of Cravioto-Lagos et al..Source: §1 · p. 2
- The proof refines Cravioto-Lagos et al.’s recursive strategy by selecting the most frequent unused color and allowing the number of steps to grow with c.Balancing the step count against accumulated error yields the √(c log c) scale, heuristically linked to a birthday paradox.Source: §1 · pp. 2–3
- For every integer c ≥ 2, there exists a size threshold n_c such that any c-coloring of a Horton set of size at least n_c contains a monochromatic triangle.Source: §1 · p. 3
- Because Horton sets are a principal source of extremal constructions, their sharp lower-bound result suggests that λ3(c) may lie closer to its lower bound.The paper concludes with a conjecture on the large-color asymptotics of λ3(c).Source: §1 · p. 3
- The result improves the second-order term but not the leading constant, and the techniques appear to meet a natural barrier at the √(c log c) scale.The asymptotic argument avoids explicit thresholds; larger-order additive corrections would likely require new ideas.Source: §1 · p. 3
2 Preliminaries
The preliminaries establish notation for point sets, color classes, and asymptotic bounds. They also state a triangulation count used in the proofs.
2 Preliminaries
- A point set S is in general position when no three of its points are collinear; CH(S) denotes its convex hull, and V(CH(S)) its boundary vertices.Source: §2 · p. 3
- A c-coloring assigns each point a color in [c], and S_a denotes the subset assigned color a.The color classes S_1 through S_c are disjoint and together contain all points of S.Source: §2 · p. 3
- Every triangulation of a point set S in general position has 2|S|−|V(CH(S))|−2 triangles.Source: §2 · p. 4
- The paper uses O(b_n) for an eventual constant-factor upper bound, o(b_n) when a_n/b_n tends to zero, and a_n ~ b_n when their ratio tends to one.Source: §2 · p. 4
3 Proof of Theorem 1.1
The proof of Theorem 1.1 assumes an infinite threshold and derives a contradiction using nested color classes and blocking estimates. It develops bounds on triangular-face blockers and selected colors, including an expected-size identity from random-order color exposure combined with a triangulation inequality.
3 Proof of Theorem 1.1
- Assuming M_3(c, c - t_c) = ∞, the proof states that for every N ≥ 1 there exists a c-colored point set S in general position with |S| ≥ N.Source: §3 · p. 4
3.1 Proof of Lemma 3.1
- Lemma 3.1 gives a local blocking recursion: monochromatic triangular faces require enough points of other colors in their interiors.Triangulating the selected color class yields faces whose interior points cannot have that selected color.Source: §3 · p. 4, §3.1 · p. 5
3.2 Proof of Lemma 3.2
- Lemma 3.2 bounds the cumulative contribution of selected colors and produces a bad set whose penultimate nested set has at least 2s_c points.The products used in the bound have a birthday no-collision interpretation, which heuristically explains the √(c log c) scale.Source: §3 · p. 5, §3.2 · p. 9
- Exposing colors in a uniformly random order gives an expected next-class size equal to the surviving population of unused colors divided by c-a; combining this with the blocking inequality yields a factor of c-a.The convex-hull restriction is performed after each exposure step.Source: §3.2 · p. 9
4 Proof of Theorem 1.3
The proof establishes the Horton-set bound by induction on colors, using the recursive binary structure and parity to find a monochromatic triangle with the required interior-point limit.
4 Proof of Theorem 1.3
- Every sufficiently large Horton set colored with at most c colors contains the monochromatic triangle required by Theorem 1.3.Source: §4 · pp. 9–10
- Among 2c+1 consecutive points, three share a color, and two have indices of the same parity, producing an even gap at most 2c.Source: §4 · pp. 9–10
- Writing the gap as 2st identifies a recursive subset where the matching points lie in different children, with odd within-subset separation t.Source: §4 · p. 10
- For an opposite-child point of the same color, the triangle has at most t−1 interior points, as bounded by the Horton-set ordering lemma.Source: §4 · p. 10
- Induction on c reduces the no-match case to a child Horton set colored with at most c−1 colors, while island containment preserves its triangle's interior-point count in H.Source: §4 · p. 10