1 Search Results for "Hubai, Tamás"

Document

DOI: 10.4230/LIPIcs.SoCG.2020.47

Almost-Monochromatic Sets and the Chromatic Number of the Plane

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

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

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.

Cite as

Nóra Frankl, Tamás Hubai, and Dömötör Pálvölgyi. Almost-Monochromatic Sets and the Chromatic Number of the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.47,
  author =	{Frankl, N\'{o}ra and Hubai, Tam\'{a}s and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
  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 =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.47},
  URN =		{urn:nbn:de:0030-drops-122054},
  doi =		{10.4230/LIPIcs.SoCG.2020.47},
  annote =	{Keywords: discrete geometry, Hadwiger-Nelson problem, Euclidean Ramsey theory}
}

Refine by Author
1 Frankl, Nóra
1 Hubai, Tamás
1 Pálvölgyi, Dömötör

Refine by Classification
1 Mathematics of computing → Graph coloring
1 Theory of computation → Computational geometry

Refine by Keyword
1 Euclidean Ramsey theory
1 Hadwiger-Nelson problem
1 discrete geometry

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Hubai, Tamás"

Almost-Monochromatic Sets and the Chromatic Number of the Plane

Abstract

Cite as

Thanks for your feedback!

Could not send message