This article is cited in 2 papers

Asymptotics of the Independence Number of a Random Subgraph of the Graph $G(n,r,<s)$

A. M. Raigorodskii^abcd, V. S. Karas<sup>b

a</sup> Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
^b Lomonosov Moscow State University
^c Caucasus Mathematical Center, Adyghe State University, Maikop
^d Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude

Abstract: 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.

UDC: 519

Received: 12.12.2020

DOI: 10.4213/mzm12722

 English version: Mathematical Notes, 2022, 111:1, 124–131

Bibliographic databases:

• 
• 
•