Monochromatic triangles found in many-colored point sets with fewer inside points
Almost Empty Monochromatic Triangles With Many Colors
Computational Geometry
Summary
The paper studies coloring points on a flat surface using multiple colors and looks for single-color triangles that have only a few points inside them. The authors refine previous work to show that as the number of colors grows large, it’s easier to find such triangles with fewer inside points than before thought. They also analyze a special type of point arrangement called Horton sets and confirm that a known lower limit on how many points can be inside the triangle is exact for these sets. Finally, they offer a guess about how the number of inside points behaves when there are many colors.
What this means in practice
- •For computational geometers: Use improved bounds on coloring point sets to analyze or optimize algorithms that detect colored geometric configurations.
- •For graph drawing specialists: Incorporate tighter bounds on monochromatic structures to control visual complexity in multi-colored planar graph layouts.
A theory result. No direct application yet.
Authors
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
Abstract
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 $λ_3(c)$ be the least integer such that $\mathsf{M}_3(c,λ_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq λ_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: $$λ_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 $λ_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $λ_3(c)$.