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
HTML articles powered by AMS MathViewer

by A. Ya. Kanel-Belov, V. A. Voronov and D. D. Cherkashin
Translated by: D. D. Cherkashin

St. Petersburg Math. J. 29 (2018), 761-775

DOI: https://doi.org/10.1090/spmj/1515

Published electronically: July 26, 2018

PDF | Request permission

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 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 10.1002/(SICI)1097-0118(199809)29:1<17::AID-JGT3>3.0.CO;2-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 10.1016/S0012-365X(01)00183-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 10.1007/s00454-004-1092-8
K. J. Falconer, The realization of distances in measurable subsets covering $\textbf {R}^{n}$, J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189. MR 629593, DOI 10.1016/0097-3165(81)90014-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 10.1007/s00454-016-9769-3
H. Hadwiger and H. Debrunner, Kombinatorische Geometrie in der Ebene, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], No. 2, Université de Genève, Institut de Mathématiques, Genève, 1960 (German). MR 0120559
P. D. Johnson, Coloring abelian groups, Discrete Math. 40 (1982), no. 2-3, 219–223. MR 676727, DOI 10.1016/0012-365X(82)90122-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 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 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 10.1112/S0025579300004903
Oren Nechushtan, On the space chromatic number, Discrete Math. 256 (2002), no. 1-2, 499–507. MR 1927575, DOI 10.1016/S0012-365X(00)00406-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, DOI 10.1002/9781118033203
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 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 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 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 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 10.1016/S0097-3165(03)00102-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 10.1016/0097-3165(73)90020-4