2026-08-17T16:50:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12205 2024-03-12T11:56:56Z ddc:004 open_access

Almost-Monochromatic Sets and the Chromatic Number of the Plane Frankl, Nóra Hubai, Tamás Pálvölgyi, Dömötör discrete geometry Hadwiger-Nelson problem Euclidean Ramsey theory In a colouring of ℝ^d a pair (S,s₀) with S ⊆ ℝ^d and with s₀ ∈ S is almost-monochromatic if S⧵{s₀} is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs (S,s₀) in colourings of ℝ^d, ℤ^d, and of ℚ under some restrictions on the colouring. Among other results, we characterise those (S,s₀) with S ⊆ ℤ for which every finite colouring of ℝ without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of (S,s₀). We also show that if S ⊆ ℤ^d and s₀ is outside of the convex hull of S⧵{s₀}, then every finite colouring of ℝ^d without a monochromatic similar copy of ℤ^d contains an almost-monochromatic similar copy of (S,s₀). Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of χ(ℝ²) ≥ 5. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nóra Frankl and Tamás Hubai and Dömötör Pálvölgyi 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.47 urn:nbn:de:0030-drops-122054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.47 eng https://creativecommons.org/licenses/by/3.0/legalcode