On Stability of the Independence Number of a Certain Distance Graph
P. A. Ogarok, Andrei Mikhailovich Raigorodskii · Problems of Information Transmission · 2020
We study the asymptotic behavior of the independence number of a random subgraph of a certain ( r , s )-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.