Geodesic
Asymptotics of the Independence Number of a Random Subgraph of the Graph~$G(n,r,$
Matematičeskie zametki, Tome 111 (2022) no. 1, pp. 107-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

The probabilistic version of a classical problem of extremal combinatorics is considered. The stability theorem which says that the independence number of a random subgraph of the graph $G(n,r,s)$ remains asymptotically constant when edges are randomly removed is generalized to the case of nonconstant parameters.
Keywords: graph $G(n,r,s)$, independence number, random subgraph, $s$-intersecting set, asymptotics. 
@article{MZM_2022_111_1_a9,
     author = {A. M. Raigorodskii and V. S. Karas},
     title = {Asymptotics of the {Independence} {Number} of a {Random} {Subgraph} of the {Graph~}$G(n,r,<s)$},
     journal = {Matemati\v{c}eskie zametki},
     pages = {107--116},
     publisher = {mathdoc},
     volume = {111},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_111_1_a9/}
}
TY  - JOUR
AU  - A. M. Raigorodskii
AU  - V. S. Karas
TI  - Asymptotics of the Independence Number of a Random Subgraph of the Graph~$G(n,r,
JO  - Matematičeskie zametki
PY  - 2022
SP  - 107
EP  - 116
VL  - 111
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_111_1_a9/
LA  - ru
ID  - MZM_2022_111_1_a9
ER  - 
%0 Journal Article
%A A. M. Raigorodskii
%A V. S. Karas
%T Asymptotics of the Independence Number of a Random Subgraph of the Graph~$G(n,r,
%J Matematičeskie zametki
%D 2022
%P 107-116
%V 111
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_111_1_a9/
%G ru
%F MZM_2022_111_1_a9
A. M. Raigorodskii; V. S. Karas. Asymptotics of the Independence Number of a Random Subgraph of the Graph~$G(n,r,

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

[2] A. J. W. Hilton, E. C. Milner, “Some intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 18 (1967), 369–384 | DOI | Zbl

[3] P. Frankl, “On intersecting families of finite sets”, J. Combin. Theory Ser. A, 24 (1978), 146–161 | DOI | Zbl

[4] R. Ahlswede, L. H. Khachatrian, “The complete nontrivial-intersection theorem for systems of finite sets”, J. Combin. Theory Ser. A, 76 (1996), 121–138 | DOI | Zbl

[5] A. Kupavskii, “Degree versions of theorems on intersecting families via stability”, J. Combin. Theory Ser. A, 168 (2019), 272–287 | DOI | Zbl

[6] P. Frankl, A. Kupavskii, “Simple juntas for shifted families”, Discrete Anal., 14 (2020), Paper No. 14 | MR

[7] P. Frankl, A. Kupavskii, “Sharp results concerning disjoint cross-intersecting families”, European J. Combin., 86 (2020), 103089 | DOI | Zbl

[8] A. Kupavskii, D. Zakharov, “Regular bipartite graphs and intersecting families”, J. Combin. Theory Ser. A, 155 (2018), 180–189 | DOI | Zbl

[9] P. Frankl, A. Kupavskii, “Incompatible intersection properties”, Combinatorica, 39:6 (2019), 1255–1266 | DOI | Zbl

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

[11] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundamenta Informatica, 145 (2016), 359–369 | DOI | Zbl

[12] A. B. Kupavskii, A. A. Sagdeev, “Teoriya Ramseya v prostranstve s chebyshevskoi metrikoi”, UMN, 75:5 (2020), 191–192 | DOI | MR | Zbl

[13] A. M. Raigorodskii, D. D. Cherkashin, “Ekstremalnye zadachi v raskraskakh gipergrafov”, UMN, 75:1 (2020), 95–154 | DOI | MR | Zbl

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

[15] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, Springer, 2013, 429–460 | MR | Zbl

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

[17] M. M. Ipatov, M. M. Koshelev, A. M. Raigorodskii, “Modulyarnost nekotorykh distantsionnykh grafov”, Dokl. AN, 490:1 (2020), 71–73 | DOI | Zbl

[18] A. M. Raigorodskii, M. M. Koshelev, “Novye otsenki kliko-khromaticheskikh chisel grafov Dzhonsona”, Dokl. AN, 490:1 (2020), 78–80 | DOI | Zbl

[19] A. M. Raigorodskii, M. M. Koshelev, “New bounds on clique-chromatic numbers of Johnson graphs”, Discrete Appl. Math., 283 (2020), 724–729 | DOI | Zbl

[20] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Ob odnom obobschenii knezerovskikh grafov”, Matem. zametki, 107:3 (2020), 351–365 | DOI | MR | Zbl

[21] B. Bollobas, B. P. Narayanan, A. Raigorodskii, “On the stability of the Erdos–Ko–Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78 | DOI | Zbl

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

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

[24] J. Balogh, B. Bollobás, B. P. Narayanan, “Transference for the Erdős–Ko–Rado theorem”, Forum Math. Sigma, 3 (2015), Paper No. e23 | MR

[25] S. Kiselev, A. Kupavskii, “Sharp Bounds for the Chromatic Number of Random Kneser Graphs”, Acta Math. Univ. Comenian. (N.S.), 88:3 (2019), 861–865 | MR

[26] M. Alishahi, H. Hajiabolhassan, “Chromatic Number of Random Kneser Hypergraphs”, J. Combin. Theory Ser. A, 154 (2018), 1–20 | DOI | Zbl

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

[28] A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Combin., 25 (2018), 4–52 | DOI | Zbl

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

[30] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | Zbl

[31] S. Das, T. Tran, “Removal and stability for Erdős–Ko–Rado”, SIAM J. Discrete Math., 30 (2016), 1102–1114 | DOI | Zbl

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

[33] N. M. Derevyanko, S. G. Kiselev, “Chisla nezavisimosti sluchainykh podgrafov nekotorogo distantsionnogo grafa”, Probl. peredachi inform., 53 (2017), 307–318 | MR | Zbl

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

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

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

[37] M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discrete Appl. Math., 267 (2019), 209–214 | DOI | Zbl

[38] M. M. Pyaderkin, “O porogovoi veroyatnosti dlya ustoichivosti nezavisimykh mnozhestv v distantsionnom grafe”, Matem. zametki, 106:2 (2019), 280–294 | DOI | MR | Zbl

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

[40] F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v podgrafakh grafa Dzhonsona”, Dokl. AN, 499:1 (2021), 40–43 | DOI | Zbl