On Threshold Probability for the Stability of Independent Sets in Distance Graphs

M. M. Pyaderkin

Matematičeskie zametki, Tome 106 (2019) no. 2, pp. 280-294.

Résumé

This paper considers the so-called distance graph $G(n,r,s)$; its vertices can be identified with the $r$-element subsets of the set $\{1,2,\dots,n\}$, and two vertices are joined by an edge if the size of the intersection of the corresponding subsets equals $s$. Note that, in the case $s=0$, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős–Ko–Rado problem; they also play an important role in combinatorial geometry and coding theory. We study properties of random subgraphs of the graph $G(n,r,s)$ in the Erdős–Rényi model, in which each edge is included in the subgraph with a certain fixed probability $p$ independently of the other edges. It is known that if $r>2s+1$, then, for $p=1/2$, the size of an independent set is asymptotically stable in the sense that the independence number of a random subgraph is asymptotically equal to that of the initial graph $G(n,r,s)$. This gives rise to the question of how small $p$ must be for asymptotic stability to cease. The main result of this paper is the answer to this question.

Détail

Keywords: random graph, distance graph, independence number, threshold probability.

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 | Zbl

[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 (337) (2001), 107–146 | DOI | MR | Zbl

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

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

[6] J. Balogh, A. V. Kostochka, A. M. 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, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2007, 202–248 | MR

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

[9] P. K. Agarwal, J. Pach, Combinatorial Geometry, John Wiley and Sons, New York, 1995 | MR | Zbl

[10] 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, Springer, Budapest, 2002, 649–666 | MR | Zbl

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

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

[13] V. G. Boltyanski, H. Martini, P. S. Soltan, Excursions into Combinatorial Geometry, Springer-Verlag, Berlin, 1997 | 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 | Zbl

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

[18] B. Bollobás, Random Graphs, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

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

[20] V. F. Kolchin, Sluchainye grafy, 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. AN, 457:4 (2014), 383–387 | DOI | 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 | MR | Zbl

[23] M. M. Pyaderkin, “Chisla nezavisimosti sluchainykh podgrafov nekotorogo distantsionnogo grafa”, Matem. zametki, 99:2 (2016), 288–297 | DOI | MR | Zbl

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

[25] M. M. Pyaderkin, “Chisla nezavisimosti sluchainykh podgrafov distantsionnykh grafov”, Matem. zametki, 99:4 (2016), 564–573 | DOI | MR | Zbl

[26] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O khromaticheskikh chislakh distantsionnykh grafov, blizkikh k knezerovskim”, Dokl. AN, 468:3 (2016), 247–250 | DOI | Zbl

[27] A. S. Gusev, “Novaya verkhnyaya otsenka khromaticheskogo chisla sluchainogo podgrafa distantsionnogo grafa”, Matem. zametki, 97:3 (2015), 342–349 | DOI | MR | Zbl

[28] A. Kupavskii, “On random subgraphs of Kneser and Schrijver graphs”, J. Combin. Theory Ser. A, 141 (2016), 8–15 | DOI | MR | Zbl

[29] S. G. Kiselev, A. M. Raigorodskii, “O khromaticheskom chisle sluchainogo podgrafa knezerovskogo grafa”, Dokl. AN, 476:4 (2017), 375–376 | DOI | Zbl

[30] M. M. Pyaderkin, A. M. Raigorodskii, “O sluchainykh podgrafakh knezerovskogo grafa i ego obobschenii”, Dokl. AN, 470:4 (2016), 384–386 | DOI | Zbl

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

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

[33] A. M. Raigorodskii, “Ob ustoichivosti chisla nezavisimosti sluchainogo podgrafa”, Dokl. AN, 477:6 (2017), 649–651 | DOI | Zbl

[34] M. Pyaderkin, “On the stability of some Erdős–Ko–Rado type results”, Discret. Math., 340:4 (2017), 822–831 | DOI | MR | Zbl

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

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

[37] L. E. Shabanov, A. M. Raigorodskii, “Turán type results for distance graphs”, Discrete Comput. Geom., 56:3 (2016), 814–832 | DOI | MR | Zbl

[38] F. A. Pushnyakov, “O chisle reber v indutsirovannykh podgrafakh spetsialnogo distantsionnogo grafa”, Matem. zametki, 99:4 (2016), 550–558 | DOI | MR | Zbl

[39] F. A. Pushnyakov, “O kolichestvakh reber v porozhdennykh podgrafakh nekotorykh distantsionnykh grafov”, Matem. zametki, 105:4 (2019), 592–602 | DOI

[40] F. A. Pushnyakov, “Novaya otsenka chisla reber v indutsirovannykh podgrafakh spetsialnogo distantsionnogo grafa”, Probl. peredachi inform., 51:4 (2015), 71–77 | Zbl

[41] N. M. Derevyanko, S. G. Kiselev, “Chisla nezavisimosti sluchainykh podgrafov nekotorogo distantsionnogo grafa”, Probl. peredachi inform., 53:4 (2017), 3–15

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

[43] József Balogh, Béla Bollobás, Bhargav P. Narayanan, “Transference for the Erdős–Ko–Rado theorem”, Forum Math. Sigma, 3 (2015), e23 | MR

[44] T. Tran, S. Das, “A simple removal lemma for large nearly-intersecting families”, Electronic Notes in Discrete Math., 49 (2015), 93–99 | DOI | Zbl

[45] P. Devlin, J. Kahn, “On “stability” in the the Erdős–Ko–Rado theorem”, SIAM J. Discrete Math., 30:2 (2016), 1283–1289 | DOI | MR | Zbl

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

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