Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii

A. B. Kupavskii   ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 204 (2013) no. 10, pp. 1435-1479

Résumé

We investigate in detail some properties of distance graphs constructed on the integer lattice. Such graphs find wide applications in problems of combinatorial geometry, in particular, such graphs were employed to answer Borsuk's question in the negative and to obtain exponential estimates for the chromatic number of the space. This work is devoted to the study of the number of cliques and the chromatic number of such graphs under certain conditions. Constructions of sequences of distance graphs are given, in which the graphs have unit length edges and contain a large number of triangles that lie on a sphere of radius $1/\sqrt{3}$ (which is the minimum possible). At the same time, the chromatic numbers of the graphs depend exponentially on their dimension. The results of this work strengthen and generalize some of the results obtained in a series of papers devoted to related issues. Bibliography: 29 titles.

Détail

Keywords: distance graph, chromatic number, sphere of smallest radius.
Mots-clés : clique

Bibliographie

[1] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer-Verlag, New York, 2005 | MR | Zbl

[2] A. Soifer, The mathematical coloring book, Springer-Verlag, New York, 2009 | MR | Zbl

[3] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosveschenie, 2004, no. 8, 186–221

[4] H. Hadwiger, “Ein Überdeckungssatz für den Euklidischen Raum”, Portugaliae Math., 4 (1944), 140–144 | MR | Zbl

[5] F. Harary, Graph theory, Addison-Wesly, Reading, MA, 1969 | MR | MR | Zbl | Zbl

[6] A. M. Raigorodskii, “Borsuk's problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | DOI | DOI | MR | Zbl

[7] A. M. Raigorodskii, Khromaticheskie chisla, MTsNMO, M., 2003

[8] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, Moskva, 2007

[9] 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 | DOI

[10] P. K. Agarwal, J. Pach, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley and Sons Inc., New York, 1995 | MR | Zbl

[11] 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 | MR | Zbl

[12] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics (Budapest, Hungary, 1999), v. II, Bolyai Soc. Math. Stud., 11, Springer-Verlag, Berlin, 2002, 649–666 | MR | Zbl

[13] A. M. Raigorodskii, “On the chromatic number of a space”, Russian Math. Surveys, 55:2 (2000), 351–352 | DOI | DOI | MR | Zbl

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

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

[16] A. M. Raigorodskii, “The Erdös–Hadwiger problem and the chromatic numbers of finite geometric graphs”, Sb. Math., 196:1 (2005), 115–146 | DOI | DOI | MR | Zbl

[17] A. M. Raigorodskii, “The problems of Borsuk and Grünbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513–537 | DOI | DOI | MR | Zbl

[18] E. S. Gorskaya, I. M. Mitricheva, V. Yu. Protasov, A. M. Raigorodskii, “The problems of Borsuk and Grünbaum on lattice polytopes”, Sb. Math., 200:6 (2009), 783–801 | DOI | DOI | MR | Zbl

[19] P. Erdős, R. L. Graham, Problem proposed at the 6th Hungarian combinatorial conference, Eger, July 1981

[20] L. Lovaśz, “Self-dual polytopes and the chromatic number of distance graphs on the sphere”, Acta Sci. Math. (Szeged), 45:1–4 (1983), 317–323 | MR | Zbl

[21] J. Matoušek, Using the Borsuk–Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003 | MR | Zbl

[22] A. M. Raigorodskii, “On the chromatic numbers of spheres in Euclidean spaces”, Dokl. Math., 81:3 (2010), 379–382 | DOI | MR | Zbl

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

[24] 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 | DOI | DOI | Zbl

[25] A. M. Raigorodskii, “On distance graphs with large chromatic number but without large simplices”, Russian Math. Surveys, 62:6 (2007), 1224–1225 | DOI | DOI | MR | Zbl

[26] 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 | MR | Zbl

[27] A. M. Raigorodskii, O. I. Rubanov, “Distance graphs with large chromatic number and without large cliques”, Math. Notes, 87:3 (2010), 392–402 | DOI | DOI | MR | Zbl

[28] P. Frankl, V. Rödl, “Forbidden intersections”, Trans. Amer. Math. Soc., 300:1 (1987), 259–286 | DOI | MR | Zbl

[29] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes, II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl