Almost-Monochromatic Sets and the Chromatic Number of the Plane

Discrete & Computational Geometry - Tập 70 - Trang 753-772 - 2023
Nóra Frankl1, Tamás Hubai2, Dömötör Pálvölgyi3,4
1School of Mathematics and Statistics, The Open University, Milton Keynes, UK
2MTA-ELTE Lendület Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University (ELTE), Budapest, Hungary
3ELTE Eötvös Loránd University, Budapest, Hungary
4Alfred Renyi Institute of Mathematics, Budapest, Hungary

Tóm tắt

In a colouring of $${\mathbb {R}}^d$$ a pair $$(S,s_0)$$ with $$S\subseteq {\mathbb {R}}^d$$ and with $$s_0\in S$$ is almost-monochromatic if $$S\setminus \{s_0\}$$ is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs $$(S,s_0)$$ in colourings of  $${\mathbb {R}}^d$$ , $${\mathbb {Z}}^d$$ , and of $${\mathbb {Q}}$$ under some restrictions on the colouring. Among other results, we characterise those $$(S,s_0)$$ with $$S\subseteq {\mathbb {Z}}$$ for which every finite colouring of $${\mathbb {R}}$$ without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of $$(S,s_0)$$ . We also show that if $$S\subseteq {\mathbb {Z}}^d$$ and $$s_0$$ is outside of the convex hull of $$S\setminus \{s_0\}$$ , then every finite colouring of $${\mathbb {R}}^d$$ without a monochromatic similar copy of $${\mathbb {Z}}^d$$ contains an almost-monochromatic similar copy of $$(S,s_0)$$ . Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of $$\chi ({{\mathbb {R}}}^2)\ge 5$$ .

Tài liệu tham khảo

Erdős, P., Graham, R.L., Montgomery, P., Rothschild, B.L., Spencer, J., Straus, E.G.: Euclidean Ramsey theorems. I. J. Comb. Theory Ser. A 14, 341–363 (1973) Erdős, P., Graham, R.L., Montgomery, P., Rothschild, B.L., Spencer, J., Straus, E.G.: Euclidean Ramsey theorems. III. In: Infinite and Finite Sets (Keszthely 1973), vol. 1. Colloq. Math. Soc. János Bolyai, vol. 10, pp. 559–583. North-Holland, Amsterdam (1975) [fedja]: Comment on the problem “Almost monochromatic point set” on MathOverflow (5/20/2018). https://mathoverflow.net/q/300604 Frankl, N.: Answer to the question “Bichromatic pencils” on MathOverflow (7/27/2018). https://mathoverflow.net/questions/299616/bichromatic-pencils Graham, R.L.: Euclidean Ramsey theory. In: Handbook of Discrete and Computational Geometry, 3rd ed., pp. 281–297 (chapter 11). Chapman and Hall, Boca Raton (2017) Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1990) de Grey, A.D.N.J.: The chromatic number of the plane is at least 5. Geombinatorics 28(1), 18–31 (2018) de Grey, A.D.N.J.: Polymath proposal: finding simpler unit distance graphs of chromatic number 5 (4/10/2018). https://polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/ Hales, A.W., Jewett, R.I.: Regularity and positional games. Trans. Am. Math. Soc. 106, 222–229 (1963) Hubai, T.: Comment in “Polymath16, fourth thread: Applying the probabilistic method” (5/9/2018). https://dustingmixon.wordpress.com/2018/05/05/polymath16-fourth-thread-applying-the-probabilistic-method/#comment-4391 Pálvölgyi D. [domotorp]: Comment in “Polymath16, fourth thread: Applying the probabilistic method” (5/6/2018). https://dustingmixon.wordpress.com/2018/05/05/polymath16-fourth-thread-applying-the-probabilistic-method/#comment-4306 Pálvölgyi D. [domotorp]: Proposing the problem “Almost monochromatic point sets” on MathOverflow (11/29/2018). https://mathoverflow.net/q/300604 Rivin, I.: Answer to the question “Existence of rational orthogonal matrices” on MathOverflow (3/2/2012). https://mathoverflow.net/q/90070 Soifer, A.: The Mathematical Coloring Book. Springer, New York (2009) van der Waerden, B.L.: Beweis einer Baudetschen Vermutung. Nieuw Archief 15, 212–216 (1927)