Almost Empty Monochromatic Triangles With Many Colors

Abstract

Given integers $c\ge 2$ and $s\ge 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\ge 2$, $$\lfloor \frac{c-1}{2}\rfloor \le {\lambda }_3(c)\le c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\ge 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $${\lambda }_3(c)\le 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)$.

12 pages, 1 figure