On Threshold Probability for the Stability of Independent Sets in Distance Graphs

Abstract

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,…,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.