×

zbMATH — the first resource for mathematics

Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii. (English. Russian original) Zbl 1303.05205
Sb. Math. 204, No. 9, 1435-1479 (2013); translation from Mat. Sb. 204, No. 10, 47-90 (2013).
A unit distance graph has its vertex set in the \(n\)-dimensional Euclidian space and its edges are joint pairs of points at Euclidian distance one. Its chromatic number is known to grow exponentially with the dimension \(n\), even when the graph is restricted to points lying on a sphere \(S^{n-1}_r\) of radius \(r>1/2\). Such restrictions can contain a \(k\)-clique only if \(r\geq r_k= \sqrt{(k-1)/2k}\). The aim of the paper under review is to show that there are families \(G_n\) of unit distance graphs in \(S^{n-1}_{r_k}\) which not only have exponentially increasing chromatic numbers but also a number of \(k\)-cliques which is \(\Omega(N(G_n)^{k+ O(\log k)})\) (at least for an infinite number of dimensions).
The constructions are built on graphs on lattice points, more precisely, on appropriately normalized distance graphs on \(\{0,1,\dots, m\}^n\) restricted to points that have the same number of coordinates of each value. The results lead to asymptotic estimates of the constants involved in the exponent of \(N(G_n)\) for the number of \(k\)-cliques and in the exponential growth of the chromatic number. A linear algebra method is used to this end.

MSC:
05D10 Ramsey theory
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer-Verlag, New York, 2005 · Zbl 1086.52001 · doi:10.1007/0-387-29929-7
[2] A. Soifer, The mathematical coloring book, Springer-Verlag, New York, 2009 · Zbl 1221.05001 · doi:10.1007/978-0-387-74642-5
[3] А. Сойфер, “Хроматическое число плоскости: его прошлое, настоящее и будущее”, Матем. просвещение, 2004, \? 8, 186 – 221
[4] H. Hadwiger, “Ein U\"berdeckungssatz fu\"r den Euklidischen Raum”, Portugaliae Math., 4 (1944), 140 – 144 · Zbl 0060.40610 · eudml:114623
[5] Ф. Харари, Теория графов, Мир, М., 1973 · Zbl 0275.05101
[6] F. Harary, Graph theory, Addison-Wesly, Reading, MA, 1969 · Zbl 0182.57702
[7] А. М. Райгородский, “Проблема Борсука и хроматические числа некоторых метрических пространств”, УМН, 56:1 (2001), 107 – 146 · Zbl 1008.54018 · doi:10.1070/rm2001v056n01ABEH000358 · mi.mathnet.ru
[8] A. M. Raigorodskii, “Borsuk/s problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103 – 139 · Zbl 1008.54018 · doi:10.1070/rm2001v056n01ABEH000358
[9] А. М. Райгородский, Хроматические числа, МЦНМО, М., 2003
[10] А. М. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, 2007
[11] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, Lecture Notes in Math., Springer-Verlag, New York, 2013, 429 – 460 · Zbl 1272.05058 · doi:10.1007/978-1-4614-0110-0_23
[12] P. K. Agarwal, J. Pach, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley and Sons Inc., New York, 1995 · Zbl 0881.52001
[13] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Dolciani Math. Exp., 11, Math. Association of America, Washington, 1991 · Zbl 0784.51002
[14] L. A. Szeḱely, “Erdo\?s on unit distances and the Szemere\'di – Trotter theorems”, Paul Erdo\?s and his mathematics (Budapest, Hungary, 1999), v. II, Bolyai Soc. Math. Stud., 11, Springer-Verlag, Berlin, 2002, 649 – 666 · Zbl 1035.05037
[15] А. М. Райгородский, “О хроматическом числе пространства”, УМН, 55:2 (2000), 147 – 148 · Zbl 0966.05029 · doi:10.1070/RM2000v055n02ABEH000281 · mi.mathnet.ru
[16] A. M. Raigorodskii, “On the chromatic number of a space”, Russian Math. Surveys, 55:2 (2000), 351 – 352 · Zbl 0966.05029 · doi:10.1070/RM2000v055n02ABEH000281
[17] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1 – 24 · Zbl 0246.05020 · doi:10.1112/S0025579300004903
[18] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357 – 368 · Zbl 0498.05048 · doi:10.1007/BF02579457
[19] А. М. Райгородский, “Проблема Эрдеша – Хадвигера и хроматические числа конечных геометрических графов”, Матем. сб., 196:1 (2005), 123 – 156 · Zbl 1070.05044 · doi:10.1070/SM2005v196n01ABEH000874 · mi.mathnet.ru
[20] A. M. Raigorodskii, “The Erdo\"s – Hadwiger problem and the chromatic numbers of finite geometric graphs”, Sb. Math., 196:1 (2005), 115 – 146 · Zbl 1070.05044 · doi:10.1070/SM2005v196n01ABEH000874
[21] А. М. Райгородский, “Проблемы Борсука и Грюнбаума для решетчатых многогранников”, Изв. РАН. Сер. матем., 69:3 (2005), 81 – 108 · Zbl 1153.52301 · doi:10.1070/IM2005v069n03ABEH000537 · mi.mathnet.ru
[22] A. M. Raigorodskii, “The problems of Borsuk and Gru\"nbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513 – 537 · Zbl 1153.52301 · doi:10.1070/IM2005v069n03ABEH000537
[23] Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский, “Оценка хроматических чисел евклидова пространства методами выпуклой минимизации”, Матем. сб., 200:6 (2009), 3 – 22 · Zbl 1250.05048 · doi:10.1070/SM2009v200n06ABEH004019 · mi.mathnet.ru
[24] E. S. Gorskaya, I. M. Mitricheva, V. Yu. Protasov, A. M. Raigorodskii, “The problems of Borsuk and Gru\"nbaum on lattice polytopes”, Sb. Math., 200:6 (2009), 783 – 801 · Zbl 1250.05048 · doi:10.1070/SM2009v200n06ABEH004019
[25] P. Erdo\?s, R. L. Graham, Problem proposed at the 6th Hungarian combinatorial conference, Eger, July 1981
[26] L. Lovasź, “Self-dual polytopes and the chromatic number of distance graphs on the sphere”, Acta Sci. Math. (Szeged), 45:1 – 4 (1983), 317 – 323 · Zbl 0533.05029
[27] J. Matous\?ek, Using the Borsuk – Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003 · Zbl 1016.05001
[28] А. М. Райгородский, “О хроматических числах сфер в евклидовых пространствах”, Докл. РАН, 432:2 (2010), 174 – 177 · Zbl 1205.52018 · doi:10.1134/S1064562410030117
[29] A. M. Raigorodskii, “On the chromatic numbers of spheres in Euclidean spaces”, Dokl. Math., 81:3 (2010), 379 – 382 · Zbl 1205.52018 · doi:10.1134/S1064562410030117
[30] A. M. Raigorodskii, “On the chromatic numbers of spheres in \( {\mathbb R}^n \)”, Combinbatorica, 32:1 (2012), 111 – 123 · Zbl 1265.05312 · doi:10.1007/s00493-012-2709-9
[31] Е. Е. Демe\"хин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49 – 78 · doi:10.4213/sm7830 · mi.mathnet.ru · zbmath.org
[32] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508 – 538 · Zbl 1268.05070 · doi:10.1070/SM2013v204n04ABEH004310 · arxiv:1202.2968
[33] А. М. Райгородский, “О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов”, УМН, 62:6 (2007), 187 – 188 · Zbl 1271.05034 · doi:10.4213/rm7485 · mi.mathnet.ru
[34] A. M. Raigorodskii, “On distance graphs with large chromatic number but without large simplices”, Russian Math. Surveys, 62:6 (2007), 1224 – 1225 · Zbl 1271.05034 · doi:10.1070/RM2007v062n06ABEH004493
[35] A. M. Raigorodskii, O. I. Rubanov, “On the clique and the chromatic numbers of high-dimensional distance graphs”, Number theory and applications (Allahabad, India, 2007), Hindustan Book Agency, New Delhi, 2009, 149 – 157 · Zbl 1238.05099
[36] А. М. Райгородский, О. И. Рубанов, “О графах расстояний с большим хроматическим числом и без больших клик”, Матем. заметки, 87:3 (2010), 417 – 428 · Zbl 1206.05037 · doi:10.1134/S0001434610030119 · mi.mathnet.ru
[37] A. M. Raigorodskii, O. I. Rubanov, “Distance graphs with large chromatic number and without large cliques”, Math. Notes, 87:3 (2010), 392 – 402 · Zbl 1206.05037 · doi:10.1134/S0001434610030119
[38] P. Frankl, V. Ro\"dl, “Forbidden intersections”, Trans. Amer. Math. Soc., 300:1 (1987), 259 – 286 · Zbl 0611.05002 · doi:10.2307/2000598
[39] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes, II”, Proc. London Math. Soc. (3), 83:3 (2001), 532 – 562 · Zbl 1016.11037 · doi:10.1112/plms/83.3.532
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.