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.