2020/11/24 by Gábor Damásdi, Damásdi, Gábor, Pálvölgyi Dömötör +1 · 1 citation
Engineering · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2011.12187
openalex publication_date 2020/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that for every m there is a finite point set P in the plane such that no matter how P is three-colored, there is always a disk containing exactly m points, all of the same color. This improves a result of Pach, Tardos and Tóth who proved the same for two colors. The main ingredient of the construction is a subconstruction whose points are in convex position. Namely, we show that for every m there is a finite point set P in the plane in convex position such that no matter how P is two-colored, there is always a disk containing exactly m points, all of the same color. We also prove that for unit disks no similar construction can work, and several other results.