This article is cited in
9 papers
On Threshold Probability for the Stability of Independent Sets in Distance Graphs
M. M. Pyaderkinab a Lomonosov Moscow State University
b Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
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,\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.
Keywords:
random graph, distance graph, independence number, threshold probability.
UDC:
519.179.4 Received: 09.03.2018
Revised: 17.09.2018
DOI:
10.4213/mzm11993
Fulltext:
PDF file (564 kB)
