Abstract:
The work concerns the well-known problem of identifying the chromatic number χ(Rn) of the
space Rn, that is, finding the minimal number of colours required to colour all points of the space in such a way that any two points at distance one from each other have different colours. A new quantity generalising the chromatic number is introduced in the paper, namely, the speckledness of a subset in a fixed metric space. A series of lower bounds for the speckledness of spheres is derived. These bounds are used to
obtain general results lifting lower bounds for the chromatic number of a space to higher dimensions, generalising the well-known ‘Moser-Raisky spindle’. As a corollary of these results, the best known lower bound for the chromatic number χ(R12)⩾27 is obtained, and furthermore, the known bound χ(R4)⩾7 is reproved in several different ways.
Bibliography: 23 titles.
Keywords:
chromatic number, distance graph, speckledness of a set.
\Bibitem{Kup11}
\by A.~B.~Kupavskii
\paper On the colouring of spheres embedded in~$\mathbb R^n$
\jour Sb. Math.
\yr 2011
\vol 202
\issue 6
\pages 859--886
\mathnet{http://mi.mathnet.ru/eng/sm7676}
\crossref{https://doi.org/10.1070/SM2011v202n06ABEH004169}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2849314}
\zmath{https://zbmath.org/?q=an:1246.05057}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2011SbMat.202..859K}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000294703200012}
\elib{https://elibrary.ru/item.asp?id=19066285}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80052774458}
Linking options:
https://www.mathnet.ru/eng/sm7676
https://doi.org/10.1070/SM2011v202n06ABEH004169
https://www.mathnet.ru/eng/sm/v202/i6/p83
This publication is cited in the following 17 articles:
Danila Cherkashin, Vsevolod Voronov, “On the Chromatic Number of 2-Dimensional Spheres”, Discrete Comput Geom, 71:2 (2024), 467
Horvath A.G., “Strongly Self-Dual Polytopes and Distance Graphs in the Unit Sphere”, Acta Math. Hung., 163:2 (2021), 640–651
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403
L. I. Bogolubsky, A. M. Raigorodskii, “A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $\ell_1$ and $\ell_2$”, Math. Notes, 105:2 (2019), 180–203
A. V. Bobu, A. E. Kupriyanov, “Refinement of Lower Bounds of the Chromatic Number of a Space with Forbidden One-Color Triangles”, Math. Notes, 105:3 (2019), 329–341
Cherkashin D., Kulikov A., Raigorodskii A., “On the Chromatic Numbers of Small-Dimensional Euclidean Spaces”, Discrete Appl. Math., 243 (2018), 125–131
A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “On the chromatic number of infinitesimal plane layer”, St. Petersburg Math. J., 29:5 (2018), 761–775
Cherkashin D.D. Raigorodskii A.M., “on the Chromatic Numbers of Low-Dimensional Spaces”, Dokl. Math., 95:1 (2017), 5–6
D. D. Cherkashin, A.M. Raigorodskii, “O KhROMATIChESKIKh ChISLAKh PROSTRANSTV MALOI RAZMERNOSTI, “Doklady Akademii nauk””, Dokl. RAN, 2017, no. 1, 11
A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369
Gil Kalai, Surveys in Combinatorics 2015, 2015, 147
A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. Math., 78:1 (2014), 59–89
A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle”, Sb. Math., 205:9 (2014), 1310–1333
V. O. Manturov, “On the chromatic numbers of integer and rational lattices”, Journal of Mathematical Sciences, 214:5 (2016), 687–698
D. V. Samirov, A. M. Raigorodskii, “New lower bounds for the chromatic number of a space with forbidden isosceles triangles”, J. Math. Sci. (N. Y.), 204:4 (2015), 531–541
Andrei M. Raigorodskii, Thirty Essays on Geometric Graph Theory, 2013, 429
Raigorodskii A.M., “On the chromatic numbers of spheres in $\mathbb R^n$”, Combinatorica, 32:1 (2012), 111–123
Citation in format AMSBIB
Contact us: