Almost empty monochromatic triangles in planar point sets

详细信息    查看全文

• 作者：Deepan Basu^a ; ^{Deepan.Basu@mis.mpg.de" class="auth_mail" title="E-mail the corresponding author} ; Kinjal Basu^b ; ^{kinjal@stanford.edu" class="auth_mail" title="E-mail the corresponding author} ; Bhaswar B. Bhattacharya^b ; ^{bhaswar@stanford.edu" class="auth_mail" title="E-mail the corresponding author} ; Sandip Das^c ; ^{sandipdas@isical.ac.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Empty polygons ; Colored point sets ; Discrete geometry ; Erdős&ndash ; Szekeres theorem
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 September 2016
• 年：2016
• 卷：210
• 期：Complete
• 页码：207-213
• 全文大小：427 K

文摘

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