Almost empty monochromatic triangles in planar point sets

DOI10.1016/J.DAM.2015.05.033zbMATH Open1339.05040arXiv1410.0424OpenAlexW2034126497MaRDI QIDQ299089FDOQ299089

Authors: Deepan Basu, Kinjal Basu, Bhaswar B. Bhattacharya, Sandip Das 

Publication date: 22 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: For positive integers $c,sgeq1$, 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 $cgeq3$. In this paper we extend these results when $cgeq2$ and $sgeq1$. We prove that the least integer $lambd{a}_3(c)$ such that $M_3(c,lambd{a}_3(c))<infty$ satisfies: ${\displaystyle }$leftlfloorfrac{c-1}{2} ight floor leqlambda_3(c)leq c-2,${\displaystyle }$ where $cgeq2$. Moreover, the exact values of $M_3(c,s)$ are determined for small values of $c$ and $s$. We also conjecture that $lambd{a}_3(4)=1$, and verify it for sufficiently large Horton sets.

Full work available at URL: https://arxiv.org/abs/1410.0424

Recommendations

• Almost empty monochromatic quadrilaterals in planar point sets
• Monochromatic empty triangles in two-colored point sets
• Monochromatic empty triangles in two-colored point sets
• On almost empty monochromatic triangles and convex quadrilaterals in colored point sets
• Empty monochromatic triangles

zbMATH Keywords

discrete geometrycolored point setsempty polygonsErdős-Szekeres theorem

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Lower bounds for the number of small convex \(k\)-holes
• Planar sets with few empty convex polygons
• Planar point sets with a small number of empty convex polygons
• On \(k\)-gons and \(k\)-holes in point sets
• Konvexe Fünfecke in ebenen Punktmengen
• Chromatic variants of the Erdős--Szekeres theorem on points in convex position.
• On the Erdös-Szekeres problem
• Almost empty hexagons
• The empty hexagon theorem
• Empty convex hexagons in planar point sets
• Large bichromatic point sets admit empty monochromatic 4-gons
• Plane Graphs with Parity Constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• On empty hexagons
• Computer solution to the 17-point Erdős-Szekeres problem
• Sets with No Empty Convex 7-Gons
• Monochromatic empty triangles in two-colored point sets
• Almost empty polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computer solution of the almost empty hexagon problem
• Empty monochromatic triangles

Cited In (10)

• A note on empty balanced tetrahedra in two-colored point sets in \(\mathbb{R}^3\)
• Empty rainbow triangles in \(k\)-colored point sets
• On almost empty monochromatic triangles and convex quadrilaterals in colored point sets
• Title not available (Why is that?)
• Almost empty monochromatic quadrilaterals in planar point sets
• Monochromatic empty triangles in two-colored point sets
• Empty monochromatic triangles
• Title not available (Why is that?)
• Monochromatic empty triangles in two-colored point sets
• Title not available (Why is that?)

This page was built for publication: Almost empty monochromatic triangles in planar point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299089)