Independence numbers and chromatic numbers of the random subgraphs of some distance graphs

L. I. Bogolubsky   ; A. S. Gusev   ; M. M. Pyaderkin   ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 206 (2015) no. 10, pp. 1340-1374

Résumé

This work is concerned with the Nelson-Hadwiger classical\linebreak problem of finding the chromatic numbers of distance graphs in $\mathbb R^n$. Most consideration is given to the class of graphs $G(n, r,s)=(V(n, r), E(n,r,s))$ defined as follows: \begin{gather*} V(n, r)=\bigl\{\mathbf{x}=(x_1,\dots,x_n) : x_i\in\{0, 1\},\, x_1+\dots+x_n=r\bigr\}, \\ E(n,r,s)=\bigl\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\bigr\}, \end{gather*} where $(\mathbf{x}, \mathbf{y})$ is the Euclidean inner product. In particular, the chromatic number of $G(n,3,1)$ was recently found by Balogh, Kostochka and Raigorodskii. The objects of the study are the random subgraphs $\mathscr{G}(G(\!n,r,s\!), p)$ whose edges are independently taken from the set $E(n,r,s)$, each with probability $p$. The independence number and the chromatic number of such graphs are estimated both from below and from above. In the case when $r-s$ is a prime power and $r\leq 2s+1$, the order of growth of $\alpha(\mathscr{G}(G(n,r,s), p))$ and $\chi(\mathscr{G}(G(n,r,s), p))$ is established. Bibliography: 51 titles.

Détail

Keywords: random graph, distance graph, independence number, chromatic number.

Bibliographie

[1] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005, xii+499 pp. | DOI | MR | Zbl

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

[3] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., John Wiley Sons, Inc., New York, 1990, xii+196 pp. | MR | Zbl

[4] A. M. Raigorodskii, Veroyatnost i algebra v kombinatorike, 3-e izd., MTsNMO, M., 2015, 48 pp.

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

[6] J. Balogh, A. Kostochka, A. Raigorodskii, “Coloring some finite sets in $\mathbb R^n$”, Discuss. Math. Graph Theory, 33:1 (2013), 25–31 | DOI | MR | Zbl

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

[8] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, Springer, New York, 2013, 429–460 | DOI | MR | Zbl

[9] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2015, 136 pp. | Zbl

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

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

[12] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer, New York, 2009, xxx+607 pp. | DOI | MR | Zbl

[13] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Dolciani Math. Exp., 11, Math. Assoc. America, Washington, DC, 1991, xvi+333 pp. | MR | Zbl

[14] P. Erdős, A. Rényi, “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[15] P. Erdős, A. Rényi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 | MR | Zbl

[16] P. Erdős, A. Rényi, “On the evolution of random graphs”, Bull. Inst. Internat. Statist., 38:4 (1961), 343–347 | MR | Zbl

[17] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011, 136 pp.

[18] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp. | DOI | MR | Zbl

[19] V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | MR | Zbl | Zbl

[20] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000, xii+333 pp. | DOI | MR | Zbl

[21] B. Bollobás, “The chromatic number of random graphs”, Combinatorica, 8:1 (1988), 49–55 | DOI | MR | Zbl

[22] T. Łuczak, “The chromatic number of random graphs”, Combinatorica, 11:1 (1991), 45–54 | DOI | MR | Zbl

[23] K. Weber, “On the independence number of random subgraphs of the $n$-cube”, Random graphs {'}85 (Poznań, 1985), North-Holland Math. Stud., 144, Ann. Discrete Math., 33, North-Holland, Amsterdam, 1987, 333–337 | MR | Zbl

[24] M. Krivelevich, B. Sudakov, “Pseudo-random graphs”, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006, 199–262 | DOI | MR | Zbl

[25] F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.–Menlo Park, Calif.–London, 1969, ix+274 pp. | MR | MR | Zbl | Zbl

[26] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., Wiley-Interscience [John Wiley Sons], New York, 2000, xviii+301 pp. | DOI | MR | Zbl

[27] D. G. Larman, “A note on the realization of distances within sets in Euclidean space”, Comment. Math. Helv., 53:4 (1978), 529–535 | DOI | MR | Zbl

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

[29] V. G. Boltyanski, H. Martini, P. S. Soltan, Excursions into combinatorial geometry, Universitext, Springer-Verlag, Berlin, 1997, xiv+418 pp. | DOI | MR | Zbl

[30] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in contemporary mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2008, 202–247 | MR | Zbl

[31] A. M. Raigorodskii, “Around Borsuk's hypothesis”, J. Math. Sci. (N. Y.), 154:4 (2008), 604–623 | DOI | MR | Zbl

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

[33] 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

[34] A. È. Guterman, V. K. Lyubimov, A. M. Raigorodskii, S. A. Usachev, “On independence numbers of distance graphs with vertices in $\{-1,0,1\}^n$: estimates, conjectures, and applications to the Nelson–Erdős–Hadwiger problem and the Borsuk problem”, J. Math. Sci. (N. Y.), 165:6 (2010), 689–709 | DOI | MR | Zbl

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

[36] A. Raigorodskii, A. Kupavskii, “Counterexamples to Borsuk's conjecture on spheres of small radii”, Moscow J. Combin. Number Theory, 2:4 (2012), 27–48 | MR | Zbl

[37] E. I. Ponomarenko, A. M. Raigorodskii, “An improvement of the Frankl–Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges”, Dokl. Math., 89:1 (2014), 59–60 | DOI | DOI | MR | Zbl

[38] E. I. Ponomarenko, A. M. Raigorodskii, “New estimates in the problem of the number of edges in a hypergraph with forbidden intersections”, Problems Inform. Transmission, 49:4 (2013), 384–390 | DOI | MR | Zbl

[39] M. Hall, Jr., Combinatorial theory, Blaisdell Publishing Co., Waltham, Mass.–Toronto, Ont.–London, 1967, x+310 pp. | MR | MR | Zbl | Zbl

[40] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, Parts I, II, North-Holland Math. Library, 16, North-Holland Publishing Co., Amsterdam–New York–Oxford, 1977 | MR | MR | Zbl | Zbl

[41] V. Rödl, “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78 | DOI | MR | Zbl

[42] J. Matoušek, Using the Borsuk–Ulam theorem, Lectures on topological methods in combinatorics and geometry, Universitext, Springer, Berlin, 2003, xii+196 pp. | MR | Zbl

[43] P. Erdős, Chao Ko, R. Rado, “Intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 12:1 (1961), 313–320 | DOI | MR | Zbl

[44] M. Deza, P. Frankl, “Erdős–Ko–Rado theorem – 22 years later”, SIAM J. Algebraic Discrete Methods, 4:4 (1983), 419–431 | DOI | MR | Zbl

[45] B. Bollobás, P. Erdős, “Cliques in random graphs”, Math. Proc. Cambridge Philos. Soc., 80:3 (1976), 419–427 | DOI | MR | Zbl

[46] Zs. Baranyai, “On the factorization of the complete uniform hypergraph”, Infinite and finite sets, Colloq., dedicated to P. Erdős on his 60th birthday (Keszthely, 1973), v. I, Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam, 1973, 91–108 | MR | Zbl

[47] A. M. Raigorodskii, “The Borsuk problem for $(0,1)$-polyhedra and cross polytopes”, Dokl. Math., 61 (2), 256–259 | MR | Zbl

[48] A. M. Raigorodskii, “Borsuk's problem for $(0,1)$-polytopes and cross-polytopes”, Dokl. Math., 65:3 (2002), 413–416 | MR | Zbl

[49] A. M. Raigorodskii, “The problem of Borsuk, Hadwiger, and Grünbaum for some classes of polytopes and graphs”, Dokl. Math., 67:1 (2003), 85–89 | MR | Zbl

[50] K. A. Mikhailov, A. M. Raigorodskii, “On the Ramsey numbers for complete distance graphs with vertices in $\{0,1\}^n$”, Sb. Math., 200:12 (2009), 1789–1806 | DOI | DOI | MR | Zbl

[51] P. Erdős, G. Szekeres, “A combinatorial problem in geometry”, Compositio Math., 2 (1935), 463–470 | MR | Zbl