Almost Empty Monochromatic Triangles in Planar Point Sets

Abstract

For positive integers $c,s\ge 1$, let $M_3(c,s)$ be the least integer such that any set of at least $M_3(c,s)$ points in the plane, no three on a line and colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. The case $s=0$, which corresponds to empty monochromatic triangles, has been studied extensively over the last few years. In particular, it is known that $M_3(1,0)=3$, $M_3(2,0)=9$ and $M_3(c,0)=\infty$, for $c\ge 3$. In this paper we extend these results when $c\ge 2$ and $s\ge 1$. We prove that the least integer ${\lambda }_3(c)$ such that $M_3(c,{\lambda }_3(c))<\infty$ satisfies: $$\lfloor \frac{c-1}{2}\rfloor \le {\lambda }_3(c)\le c-2,$$ where $c\ge 2$. Moreover, the exact values of $M_3(c,s)$ are determined for small values of $c$ and $s$. We also conjecture that ${\lambda }_3(4)=1$, and verify it for sufficiently large Horton sets.

Revised. 10 Pages, 2 figures. To appear in Discrete Applied Mathematics