|
This article is cited in 8 scientific papers (total in 8 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.
Received: 09.03.2018 Revised: 17.09.2018
Citation:
M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Mat. Zametki, 106:2 (2019), 280–294; Math. Notes, 106:2 (2019), 274–285
Linking options:
https://www.mathnet.ru/eng/mzm11993https://doi.org/10.4213/mzm11993 https://www.mathnet.ru/eng/mzm/v106/i2/p280
|
|