A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $\ell_1$ and $\ell_2$

L. I. Bogolubsky ; A. M. Raigorodskii

Matematičeskie zametki, Tome 105 (2019) no. 2, pp. 187-213.

Résumé

A particular class of estimates related to the Nelson–Erdős–Hadwiger problem is studied. For two types of spaces, Euclidean and spaces with metric $\ell_1$, certain series of distance graphs of small dimensions are considered. Independence numbers of such graphs are estimated by using the linear-algebraic method and combinatorial observations. This makes it possible to obtain certain lower bounds for the chromatic numbers of the spaces mentioned above and, for each case, specify a series of graphs leading to the strongest results.

Détail

Keywords: chromatic number, chromatic number of a metric space, independence number, linear-algebraic method, distance graph.

Bibliographie

[1] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of Its Creators, Springer, New York, 2009 | MR | Zbl

[2] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR

[3] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | MR | Zbl

[4] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | MR

[5] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (337) (2001), 107–146 | DOI | MR | Zbl

[6] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | DOI | MR | Zbl

[7] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005 | MR | Zbl

[8] K. Cantwell, “Finite Euclidean Ramsey theory”, J. Combin. Theory Ser. A, 73:2 (1996), 273–285 | DOI | MR | Zbl

[9] K. B. Chilakamarri, “The unit-distance graph problem: a brief survey and some new results”, Bull. Inst. Combin. Appl., 8 (1993), 39–60 | MR | Zbl

[10] J. Cibulka, “On the chromatic number of real and rational spaces”, Geombinatorics, 18:2 (2008), 53–65 | MR | Zbl

[11] G. Exoo, D. Ismailescu, On the Chromatic Number of ${\mathbb R}^n$ for Small Values of $n$, 2014, arXiv: http://arxiv.org/abs/1408.2002 | Zbl

[12] G. Exoo, D. Ismailescu, M. Lim, “On the chromatic number of ${\mathbb R}^4$”, Discrete Comput. Geom., 52:2 (2014), 416–423 | DOI | MR | Zbl

[13] M. Kahle, B. Taha, “New lower bounds on $\chi({\mathbb R}^d)$, $d=8,\dots,12$”, Geombinatorics, 24:3 (2015), 109–116 | MR | Zbl

[14] A. B. Kupavskii, A. M. Raigorodskii, “O khromaticheskom chisle $\mathbb R^9$”, Fundament. i prikl. matem., 14:5 (2008), 139–154 | MR

[15] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[16] Z. Nagy, “A certain constructive estimate of the Ramsey number”, Mat. Lapok, 23:301–302 (1972), 26 | MR

[17] O. Nechushtan, “Note on the space chromatic number”, Discrete Math., 256:1-2 (2002), 499–507 | DOI | MR | Zbl

[18] D. D. Cherkashin, A. M. Raigorodskii, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Dokl. AN, 472:1 (2017), 11–12 | DOI | Zbl

[19] D. Cherkashin, A. Kulikov, A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete Appl. Math., 243 (2018), 125–131 | DOI | MR | Zbl

[20] A. E. Guterman, V. K. Lyubimov, A. M. Raigorodskii, A. S. Usachev, “O chislakh nezavisimosti grafov rasstoyanii s vershinami v $\{-1,0,1\}^n$”, Matem. zametki, 86:5 (2009), 794–796 | DOI | MR | Zbl

[21] V. K. Lyubimov, A. M. Raigorodskii, “O nizhnikh otsenkakh chisel nezavisimosti distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Dokl. AN, 427:4 (2009), 458–460 | Zbl

[22] A. M. Raigorodskii, A. B. Kupavskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, European Conference on Combinatorics, Graph Theory and Applications, Electron. Notes Discrete Math., 34, Elsevier Sci. B. V., Amsterdam, 2009, 435–439 | DOI | MR | Zbl

[23] P. Frankl, R. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[24] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (332) (2000), 147–148 | DOI | MR | Zbl

[25] M. Benda, M. Perles, “Colorings of metric spaces”, Geombinatorics, 9:3 (2000), 113–126 | MR | Zbl

[26] Z. Füredi, J.-H. Kang, “Distance graphs on ${\mathbb Z}^n$ with $l_1$-norm”, Theoret. Comput. Sci., 319:1-3 (2004), 357–366 | MR | Zbl

[27] Y. Katznelson, “Chromatic numbers of Cayley graphs on $\mathbb{Z}$ and recurrence”, Combinatorica, 21:2 (2001), 211–219 | DOI | MR | Zbl

[28] A. B. Kupavskii, “O raskraskakh sfer, vlozhennykh v $\mathbb R^n$”, Matem. sb., 202:6 (2011), 83–110 | DOI | MR | Zbl

[29] A. B. Kupavskii, “O podnyatii otsenki khromaticheskogo chisla ${\mathbb R}^n$ v bolshuyu razmernost”, Dokl. AN, 429:3 (2009), 305–308 | Zbl

[30] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s dvumya zapreschennymi rasstoyaniyami”, Dokl. AN, 408:5 (2006), 601–604 | Zbl

[31] N. G. Moschevitin, A. M. Raigorodskii, “O raskraskakh prostranstva $\mathbb R^n$ s neskolkimi zapreschennymi rasstoyaniyami”, Matem. zametki, 81:5 (2007), 733–743 | DOI | MR | Zbl

[32] A. M. Raigorodskii, I. M. Shitova, “O khromaticheskikh chislakh veschestvennykh i ratsionalnykh prostranstv s veschestvennymi ili ratsionalnymi zapreschennymi rasstoyaniyami”, Matem. sb., 199:4 (2008), 107–142 | DOI | MR | Zbl

[33] A. M. Raigorodskii, I. M. Shitova, “O khromaticheskom chisle evklidova prostranstva i o probleme Borsuka”, Matem. zametki, 83:4 (2008), 636–639 | DOI | MR | Zbl

[34] E. S. Gorskaya, I. M. Mitricheva, V. Yu. Protasov, A. M. Raigorodskii, “Otsenka khromaticheskikh chisel evklidova prostranstva metodami vypukloi minimizatsii”, Matem. sb., 200:6 (2009), 3–22 | DOI | MR | Zbl

[35] A. M. Raigorodskii, “O khromaticheskikh chislakh sfer v evklidovom prostranstve”, Dokl. AN, 432:2 (2010), 174–177 | MR | Zbl

[36] A. M. Raigorodskii, “On the chromatic numbers of spheres in ${\mathbb R}^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[37] O. A. Kostina, A. M. Raigorodskii, “O nizhnikh otsenkakh khromaticheskogo chisla sfery”, Dokl. AN, 463:6 (2015), 639–641 | DOI | Zbl

[38] A. V. Berdnikov, A. M. Raigorodskii, “O khromaticheskom chisle evklidova prostranstva s dvumya zapreschennymi rasstoyaniyami”, Matem. zametki, 96:5 (2014), 790–793 | DOI | MR | Zbl

[39] A. B. Kupavskii, “On the chromatic number of ${\mathbb R}^n$ with an arbitrary norm”, Discrete Math., 311:6 (2011), 437–440 | DOI | MR

[40] A. B. Kupavskii, “Khromaticheskoe chislo ${\mathbb R}^n$ s mnozhestvom zapreschennykh rasstoyanii”, Dokl. AN, 435:6 (2010), 740–743 | MR | Zbl

[41] E. I. Ponomarenko, A. M. Raigorodskii, “Novaya nizhnyaya otsenka khromaticheskogo chisla ratsionalnogo prostranstva s odnim i dvumya zapreschennymi rasstoyaniyami”, Matem. zametki, 97:2 (2015), 255–261 | DOI | MR | Zbl

[42] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “O khromaticheskom chisle ploskosti”, Algebra i analiz, 29:5 (2017), 68–89 | MR

[43] A. A. Sagdeev, “O teoreme Frankla–Redla”, Izv. RAN. Ser. matem., 82:6 (2018), 128–157 | DOI

[44] A. A. Sagdeev, “Uluchshennaya teorema Frankla–Redlya i nekotorye ee geometricheskie sledstviya”, Probl. peredachi inform., 54:2 (2018), 45–72

[45] A. A. Sagdeev, “Eksponentsialno ramseevskie mnozhestva”, Probl. peredachi inform. (to appear)

[46] R. I. Prosanov, A. M. Raigorodskii, A. A. Sagdeev, “Uluchsheniya teoremy Frankla–Redlya i geometricheskie sledstviya”, Dokl. AN, 475:2 (2017), 137–139 | DOI | MR | Zbl

[47] R. I. Prosanov, “Verkhnie otsenki khromaticheskikh chisel evklidovykh prostranstv s zapreschennymi ramseevskimi mnozhestvami”, Matem. zametki, 103:2 (2018), 248–257 | DOI | Zbl

[48] A. M. Raigorodskii, A. A. Sagdeev, “Ob odnoi otsenke v ekstremalnoi kombinatorike”, Dokl. AN, 478:3 (2018), 271–273 | DOI | MR | Zbl

[49] A. V. Berdnikov, “Otsenka khromaticheskogo chisla evklidova prostranstva s neskolkimi zapreschennymi rasstoyaniyami”, Matem. zametki, 99:5 (2016), 783–787 | DOI | MR | Zbl

[50] A. V. Berdnikov, “Chromatic number with several forbidden distances in the space with the $\ell_q$-metric”, J. Math. Sci. (N.Y.), 227:4 (2017), 395–401 | DOI | MR | Zbl

[51] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s metrikoi $l_q$”, UMN, 59:5 (359) (2004), 161–162 | DOI | MR | Zbl

[52] L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Part 1. Preliminary version 2, Department of Computer Science, The University of Chicago, 1992

[53] https://github.com/LevBogolubsky/chrom_lower_linear_algebra