Independence Numbers of Random Subgraphs of Distance Graphs

M. M. Pyaderkin

Matematičeskie zametki, Tome 99 (2016) no. 4, pp. 564-573.

Résumé

We consider the distance graph $G(n,r,s)$, whose vertices can be identified with $r$-element subsets of the set $\{1,2,\dots,n\}$, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is $s$. For $s=0$, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of $G(n,r,s)$ in the Erdős–Rényi model, in which every edge occurs in the subgraph with some given probability $p$ independently of the other edges. We find the asymptotics of the independence number of a random subgraph of $G(n,r,s)$ for the case of constant $r$ and $s$. The independence number of a random subgraph is $\Theta(\log_2n)$ times as large as that of the graph $G(n,r,s)$ itself for $r \le 2s+1$, while for $r > 2s+1$ one has asymptotic stability: the two independence numbers asymptotically coincide.

Détail

Keywords: distance graph, random subgraph, independence number, Erdős–Ko–Rado problem, Erdős–Rényi model.

Bibliographie

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

[2] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | MR | Zbl

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

[4] A. M. Raigorodskii, “O khromaticheskikh chislakh sfer v evklidovykh prostranstvakh”, 432, no. 2, Dokl. RAN, 2010, 174–177 | MR | Zbl

[5] A. M. Raigorodskii, “On the chromatic numbers of spheres in $\mathbb R^n$”, Combinatorica, 32:1 (2012), 111–123 | 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] J. Pach, P. K. Agarwal, Combinatorial Geometry, John Wiley and Sons, New York, 1995 | MR | Zbl

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

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

[10] V. Klee, S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, The Dolciani Math. Exp., 11, Math. Assoc. America, Washington, DC, 1991 | MR | Zbl

[11] V. Boltyanski, H. Martini, P. S. Soltan, Excursions into Combinatorial Geometry, Universitext, Springer-Verlag, Berlin, 1997 | MR | Zbl

[12] 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–248 | MR | Zbl

[13] A. M. Raigorodskii, “Vokrug gipotezy Borsuka”, Geometriya i mekhanika, SMFN, 23, RUDN, M., 2007, 147–164 | MR | Zbl

[14] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey Theory, John Wiley and Sons, New York, 1990 | MR | Zbl

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

[16] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Radio i svyaz, M., 1979 | MR | MR | Zbl

[17] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Discrete Math., 213 (2000), 3–11 | DOI | MR | Zbl

[18] B. Bollobás, Random Graphs, Cambridge Stud. in Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[19] S. Janson, T. Łuczak, A. Ruciński, Random Graphs, Wiley, New York, 2000 | MR | Zbl

[20] V. F. Kolchin, Sluchainye grafy, Teoriya veroyatnostei i matematicheskaya statistika, Fizmatlit, M., 2000 | MR | Zbl

[21] L. I. Bogolyubskii, A S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov v nekotorykh posledovatelnostyakh grafov”, Dokl. RAN, 457:4 (2014), 383–387 | DOI | MR | Zbl

[22] L. I. Bogolyubskii, A S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov nekotorykh distantsionnykh grafov”, Matem. sb., 206:10 (2015), 3–36 | DOI

[23] M. M. Pyadërkin, “Chisla nezavisimosti sluchainykh podgrafov nekotorogo distantsionnogo grafa”, Matem. zametki, 99:2 (2016), 288–297

[24] M. M. Pyaderkin, “Ob ustoichivosti v teoreme Erdesha–Ko–Rado”, Dokl. RAN, 462:2 (2015), 144–147 | DOI | Zbl

[25] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78 | Zbl

[26] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundam. Inform., 2016 (to appear)

[27] P. Frankl, Z. Füredi, “Forbidding just one intersection”, J. Combin. Theory Ser. A, 39:2 (1985), 160–176 | DOI | MR | Zbl

[28] J. Matoušek, Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, Berlin, 2003 | MR | Zbl