On the chromatic number of an infinitesimal plane layer

Kanel-Belov, A.; Voronov, V.; Cherkashin, D.

doi:10.1090/spmj/1515

On the chromatic number of an infinitesimal plane layer

Authors: A. Ya. Kanel-Belov, V. A. Voronov and D. D. Cherkashin
Translated by: D. D. Cherkashin
Original publication: Algebra i Analiz, tom 29 (2017), nomer 5.
Journal: St. Petersburg Math. J. 29 (2018), 761-775
MSC (2010): Primary 05C62, 52C10
DOI: https://doi.org/10.1090/spmj/1515
Published electronically: July 26, 2018
MathSciNet review: 3724639
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract:

This paper is devoted to a natural generalization of the problem on the chromatic number of the plane. The chromatic number of the spaces $\mathbb {R}^n \times [0,\varepsilon ]^k$ is considered.

It is proved that $5 \leq \chi (\mathbb {R}^2\times [0,\varepsilon ])\leq 7$ and ${6\leq \chi (\mathbb {R}^2\times [0,\varepsilon ]^2) \leq 7}$ for $\varepsilon >0$ sufficiently small.

Also, some natural questions arising from these considerations are posed.

References

P. S. Aleksandrov and B. A. Pasynkov, Vvedenie v teoriyu razmernosti: Vvedenie v teoriyu topologicheskikh prostranstv i obshchuyu teoriyu razmernosti, Izdat. “Nauka”, Moscow, 1973 (Russian). MR 0365524
M. Axenovich, J. Choi, M. Lastrina, T. McKay, J. Smith, and B. Stanton, On the chromatic number of subsets of the Euclidean plane, Graphs Combin. 30 (2014), no. 1, 71–81. MR 3143859, DOI https://doi.org/10.1007/s00373-012-1249-9
Bruce L. Bauslaugh, Tearing a strip off the plane, J. Graph Theory 29 (1998), no. 1, 17–33. MR 1633912, DOI https://doi.org/10.1002/%28SICI%291097-0118%28199809%2929%3A1%3C17%3A%3AAID-JGT3%3E3.0.CO%3B2-H
M. Benda and M. Perles, Colorings of metric spaces, Geombinatorics 9 (2000), no. 3, 113–126. MR 1746078
Peter Brass, William Moser, and János Pach, Research problems in discrete geometry, Springer, New York, 2005. MR 2163782
Kiran B. Chilakamarri, The unit-distance graph problem: a brief survey and some new results, Bull. Inst. Combin. Appl. 8 (1993), 39–60. MR 1217358
D. Coulson, A 15-colouring of 3-space omitting distance one, Discrete Math. 256 (2002), no. 1-2, 83–90. MR 1927057, DOI https://doi.org/10.1016/S0012-365X%2801%2900183-2

J. D. Currie and R. B. Eggleton, Chromatic properties of the Euclidean plane, arXiv:1509.03667, 2015.

Geoffrey Exoo, $\epsilon $-unit distance graphs, Discrete Comput. Geom. 33 (2005), no. 1, 117–123. MR 2105753, DOI https://doi.org/10.1007/s00454-004-1092-8

K. J. Falconer, The realization of distances in measurable subsets covering ${\bf R}^{n}$, J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189. MR 629593, DOI https://doi.org/10.1016/0097-3165%2881%2990014-5

Jarosław Grytczuk, Konstanty Junosza-Szaniawski, Joanna Sokół, and Krzysztof Węsek, Fractional and $j$-fold coloring of the plane, Discrete Comput. Geom. 55 (2016), no. 3, 594–609. MR 3473669, DOI https://doi.org/10.1007/s00454-016-9769-3

H. Hadwiger and H. Debrunner, Kombinatorische Geometrie in der Ebene, Monographies de “L’Enseignement Mathématique”, No. 2, Institut de Mathématiques, Université, Genève, 1960 (German). MR 0120559

P. D. Johnson, Coloring abelian groups, Discrete Math. 40 (1982), no. 2-3, 219–223. MR 676727, DOI https://doi.org/10.1016/0012-365X%2882%2990122-4

Jeff Kahn and Gil Kalai, A counterexample to Borsuk’s conjecture, Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 60–62. MR 1193538, DOI https://doi.org/10.1090/S0273-0979-1993-00398-7

Victor Klee and Stan Wagon, Old and new unsolved problems in plane geometry and number theory, The Dolciani Mathematical Expositions, vol. 11, Mathematical Association of America, Washington, DC, 1991. MR 1133201

A. B. Kupavskiĭ, Colorings of spheres embedded in $\Bbb R^n$, Mat. Sb. 202 (2011), no. 6, 83–110 (Russian, with Russian summary); English transl., Sb. Math. 202 (2011), no. 5-6, 859–886. MR 2849314, DOI https://doi.org/10.1070/SM2011v202n06ABEH004169

A. B. Kupavskii and A. M. Raigorodskii, On the chromatic numbers of small-dimensional Euclidean spaces, Electron. Notes Discrete Math., vol. 34, Elsevier Sci., Amsterdam, 2009, pp. 435–439.

D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24. MR 319055, DOI https://doi.org/10.1112/S0025579300004903

Oren Nechushtan, On the space chromatic number, Discrete Math. 256 (2002), no. 1-2, 499–507. MR 1927575, DOI https://doi.org/10.1016/S0012-365X%2800%2900406-4

János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145

E. I. Ponomarenko and A. M. Raĭgorodskiĭ, A new lower bound for the chromatic number of the rational space, Uspekhi Mat. Nauk 68 (2013), no. 5(413), 183–184 (Russian); English transl., Russian Math. Surveys 68 (2013), no. 5, 960–962. MR 3155166, DOI https://doi.org/10.1070/rm2013v068n05abeh004865

E. I. Ponomarenko and A. M. Raĭgorodskiĭ, New lower bound for the chromatic number of a rational space with one and two forbidden distances, Mat. Zametki 97 (2015), no. 2, 255–261 (Russian, with Russian summary); English transl., Math. Notes 97 (2015), no. 1-2, 249–254. MR 3370511, DOI https://doi.org/10.4213/mzm10383

A. M. Raĭgorodskiĭ, On the chromatic number of a space, Uspekhi Mat. Nauk 55 (2000), no. 2(332), 147–148 (Russian); English transl., Russian Math. Surveys 55 (2000), no. 2, 351–352. MR 1781075, DOI https://doi.org/10.1070/rm2000v055n02ABEH000281

A. M. Raĭgorodskiĭ, The Borsuk problem and the chromatic numbers of some metric spaces, Uspekhi Mat. Nauk 56 (2001), no. 1(337), 107–146 (Russian, with Russian summary); English transl., Russian Math. Surveys 56 (2001), no. 1, 103–139. MR 1845644, DOI https://doi.org/10.1070/rm2001v056n01ABEH000358

---, Chromatic numbers, MTsNMO, Moscow, 2003. (Russian)

---, Linear-algebraic method in combinatorics, MTsNMO, Moscow, 2007. (Russian)

---, Coloring distance graphs and graphs of diameters, Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 429–460.

---, Cliques and cycles in distance graphs and graphs of diameters, Discrete geometry and algebraic combinatorics, Contemp. Math, vol. 625, Amer. Math. Soc., Providence, RI, 2014, pp. 93–109.

D. E. Raĭskiĭ, The realization of all distances in a decomposition of the space $R^{n}$ into $n+1$ parts, Mat. Zametki 7 (1970), 319–323 (Russian). MR 261446

Saharon Shelah and Alexander Soifer, Axiom of choice and chromatic number of the plane, J. Combin. Theory Ser. A 103 (2003), no. 2, 387–391. MR 1996076, DOI https://doi.org/10.1016/S0097-3165%2803%2900102-X

Alexander Soifer, Relatives of chromatic number of the plane. I, Geombinatorics 1 (1992), no. 4, 13–17. MR 1208441

Alexander Soifer, The mathematical coloring book, Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. MR 2458293

Alexander Soifer, The Hadwiger-Nelson problem, Open problems in mathematics, Springer, [Cham], 2016, pp. 439–457. MR 3526945

L. A. Székely, Erdős on unit distances and the Szemerédi-Trotter theorems, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 649–666. MR 1954746

D. R. Woodall, Distances realized by sets covering the plane, J. Combinatorial Theory Ser. A 14 (1973), 187–200. MR 310770, DOI https://doi.org/10.1016/0097-3165%2873%2990020-4