Independence Numbers of Random Subgraphs of a~Distance Graph

M. M. Pyaderkin

Matematičeskie zametki, Tome 99 (2016) no. 2, pp. 288-297.

Résumé

We consider the so-called distance graph $G(n,3,1)$, whose vertices can be identified with three-element subsets of the set $\{1,2,\dots,n\}$, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of $G(n,3,1)$ in the Erdős–Rényi model, in which each edge is included 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,3,1)$.

Détail

Keywords: distance graph, random subgraph, independence number, 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”, Dokl. RAN, 432:2 (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, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley 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, 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, 2007, 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, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley Sons, New York, 1990 | MR | Zbl

[15] Z. Nagy, “A certain constructive estimate of the Ramsey number”, Mat. Lapok, 23 (1974), 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:1-3 (2000), 3–11 | DOI | MR | Zbl

[18] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 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, 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 | 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] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distantsionnye grafy, imeyuschie bolshoe khromaticheskoe chislo i ne soderzhaschie klik ili tsiklov zadannogo razmera”, Matem. sb., 204:4 (2013), 49–78 | DOI | MR | Zbl

[24] A. M. Raigorodskii, K. A. Mikhailov, “O chislakh Ramseya dlya polnykh distantsionnykh grafov s vershinami v $\{0,1\}^n$”, Matem. sb., 200:12 (2009), 63–80 | DOI | MR | Zbl