License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.47
URN: urn:nbn:de:0030-drops-122054
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12205/
Go to the corresponding LIPIcs Volume Portal

Frankl, Nóra ; Hubai, Tamás ; Pálvölgyi, Dömötör

Almost-Monochromatic Sets and the Chromatic Number of the Plane

pdf-format:
LIPIcs-SoCG-2020-47.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{frankl_et_al:LIPIcs:2020:12205,
  author =	{N{\'o}ra Frankl and Tam{\'a}s Hubai and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi},
  title =	{{Almost-Monochromatic Sets and the Chromatic Number of the Plane}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12205},
  URN =		{urn:nbn:de:0030-drops-122054},
  doi =		{10.4230/LIPIcs.SoCG.2020.47},
  annote =	{Keywords: discrete geometry, Hadwiger-Nelson problem, Euclidean Ramsey theory}
}

Keywords: discrete geometry, Hadwiger-Nelson problem, Euclidean Ramsey theory
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI