×

Chromatic numbers of spheres. (English) Zbl 1395.05062

Summary: The chromatic number of a subset of Euclidean space is the minimal number of colors sufficient for coloring all points of this subset in such a way that any two points at the distance 1 have different colors. We give new upper bounds on chromatic numbers of spheres. This also allows us to give new upper bounds on chromatic numbers of any bounded subsets.

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Artstein-Avidan, S.; Raz, O., Weighted covering numbers of convex sets, Adv. Math., 227, 1, 730-744, (2011) · Zbl 1221.52026
[2] Artstein-Avidan, S.; Slomka, B. A., On weighted covering numbers and the Levi-hadwiger conjecture, Israel J. Math., 209, 1, 125-155, (2015) · Zbl 1339.52014
[3] Bachoc, C.; Passuello, A.; Thiery, A., The density of sets avoiding distance 1 in Euclidean space, Discrete Comput. Geom., 53, 4, 783-808, (2015) · Zbl 1327.52032
[4] Berdnikov, A. V., Estimate for the chromatic number of Euclidean space with several forbidden distances, Mat. Zametki, 99, 5, 783-787, (2016) · Zbl 1354.05043
[5] Berdnikov, A. V., Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size, Probl. Inf. Transm., 54, 1, 70-83, (2018)
[6] Berdnikov, A. V.; Raigorodskii, A. M., On the chromatic number of Euclidean space with two forbidden distances, Math. Notes, 96, 5-6, 827-830, (2014), Translation of Mat. Zametki 96 (5) (2014) 790-793 · Zbl 1408.05057
[7] Böröczky, K., Finite packing and covering, (Cambridge Tracts in Mathematics, vol. 154, (2004), Cambridge University Press, Cambridge), xviii+380 · Zbl 1061.52011
[8] Böröczky, K.; Wintsche, G., Covering the sphere by equal spherical balls, (Discrete and Computational Geometry, Algorithms Combin., vol. 25, (2003), Springer, Berlin), 235-251 · Zbl 1077.52513
[9] de Bruijn, N. G.; Erdös, P., A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math., 13, 369-373, (1951) · Zbl 0044.38203
[10] Cherkashin, D. D.; Raigorodskii, A. M., On the chromatic numbers of small-dimensional spaces, Dokl. Math., 95, 1, 5-6, (2017) · Zbl 1365.05085
[11] Cherkashin, D.; Kulikov, A.; Raigorodskii, A., On the chromatic numbers of small-dimensional Euclidean spaces, Discrete Appl. Math., 243, 125-131, (2018) · Zbl 1387.05061
[12] A.D.N.J. de Grey, The chromatic number of the plane is at least 5, 2018, ArXiv e-prints, arXiv:1804.02385; A.D.N.J. de Grey, The chromatic number of the plane is at least 5, 2018, ArXiv e-prints, arXiv:1804.02385
[13] E. DeCorte, F. Mário de Oliveira Filho, F. Vallentin, Complete positivity and distance-avoiding sets, ArXiv e-prints, 2018, arXiv:1804.09099; E. DeCorte, F. Mário de Oliveira Filho, F. Vallentin, Complete positivity and distance-avoiding sets, ArXiv e-prints, 2018, arXiv:1804.09099
[14] Falconer, K. J., The realization of distances in measurable subsets covering \(\mathbf{R}^n\), J. Combin. Theory Ser. A, 31, 2, 184-189, (1981) · Zbl 0469.05021
[15] Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256-278, (1974), Fifth Annual ACM Symposium on the Theory of Computing (Austin, Tex., 1973) · Zbl 0296.65036
[16] Kostina, O. A., On lower bounds for the chromatic number of a sphere, Math. Notes, (2018), in press
[17] Kostina, O. A.; Raigorodskii, A. M., On lower bounds for the chromatic number of a sphere, Dokl. Math., 92, 1, 500-502, (2015) · Zbl 1330.52021
[18] Kupavskiy, A., The chromatic number of the space \(\mathbb{R}^n\) with the set of forbidden distances, Dokl. Math., 82, 3, 963-966, (2010) · Zbl 1292.05147
[19] Kupavskiy, A., On the chromatic number of \(\mathbb{R}^n\) with an arbitrary norm, Discrete Math., 311, 6, 437-440, (2011) · Zbl 1235.05016
[20] Larman, D. G.; Rogers, C. A., The realization of distances within sets in Euclidean space, Mathematika, 19, 1-24, (1972) · Zbl 0246.05020
[21] Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 4, 383-390, (1975) · Zbl 0323.05127
[22] Lovász, L., Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged), 45, 1-4, 317-323, (1983), 708798 · Zbl 0533.05029
[23] Naszódi, M., On some covering problems in geometry, Proc. Amer. Math. Soc., 144, 8, 3555-3562, (2016) · Zbl 1341.52031
[24] Naszódi, M., Flavors of translative coverings, (New Trends in Intuitive Geometry, (2018), Springer, Berlin)
[25] Naszódi, M.; Polyanskii, A., Approximating set multi-covers, European J. Combin., 67, 174-180, (2018) · Zbl 1371.05203
[26] Ponomarenko, E. I.; Raigorodskii, A. M., New lower bound for the chromatic number of a rational space with one and two forbidden distances, Mat. Zametki, 97, 2, 255-261, (2015) · Zbl 1317.05064
[27] R. Prosanov, A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space, 2016, ArXiv e-prints arXiv:1610.02846; R. Prosanov, A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space, 2016, ArXiv e-prints arXiv:1610.02846
[28] Prosanov, R. I., Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets, Mat. Zametki, 103, 2, 248-257, (2018) · Zbl 1390.05071
[29] Raigorodskii, A. M., On the chromatic number of a space, Uspekhi Mat. Nauk, 55, 2(332), 147-148, (2000) · Zbl 0966.05029
[30] Raigorodskii, A. M., The Borsuk problem and the chromatic numbers of some metric spaces, Uspekhi Mat. Nauk, 56, 1(337), 107-146, (2001)
[31] Raigorodskii, A. M., On the chromatic numbers of spheres in Euclidean spaces, Dokl. Akad. Nauk, 432, 2, 174-177, (2010) · Zbl 1205.52018
[32] Raigorodskii, A. M., On the chromatic numbers of spheres in \(\mathbb{R}^n\), Combinatorica, 32, 1, 111-123, (2012) · Zbl 1265.05312
[33] Raigorodskii, A. M., Coloring distance graphs and graphs of diameters, (Thirty Essays on Geometric Graph Theory, (2013), Springer, New York), 429-460 · Zbl 1272.05058
[34] Raigorodskii, A. M., Cliques and cycles in distance graphs and graphs of diameters, (Discrete Geometry and Algebraic Combinatorics, Contemp. Math., vol. 625, (2014), Amer. Math. Soc. Providence, RI), 93-109 · Zbl 1338.52019
[35] Raigorodskii, A. M., Combinatorial geometry and coding theory, Fund. Inform., 145, 3, 359-369, (2016) · Zbl 1421.94120
[36] Rogers, C. A., A note on coverings, Mathematika, 4, 1-6, (1957) · Zbl 0079.27203
[37] Rogers, C. A., Covering a sphere with spheres, Mathematika, 10, 157-164, (1963) · Zbl 0158.19603
[38] Sagdeev, A., On a Frankl-Rödl theorem and its geometric corollaries, Electron. Notes Discrete Math., 61, 1033-1037, (2017) · Zbl 1378.05072
[39] Sagdeev, A. A.; Raigorodskii, A. M., On the chromatic number of a space with forbidden regular simplices, Dokl. Math., 95, 1, 15-16, (2017) · Zbl 1365.05099
[40] Sagdeev, A., Improved Frankl-Rödl theorem and some of its geometric consequences, Probl. Inform. Transmission, 54, 2, 140-165, (2018)
[41] Soifer, A., The mathematical coloring book, xxx+607, (2009), Springer New York, Mathematics of Coloring and the Colorful Life of Its Creators · Zbl 1221.05001
[42] Stein, S. K., Two combinatorial covering theorems, J. Combin. Theory Ser. A, 16, 391-397, (1974) · Zbl 0287.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.