On the Stability of the Independence Number in Random Distance Graphs
Abstract
We consider a random subgraph Gp(n,r,<s) of the complete distance graph G(n,r,<s) whose vertices are the r-element subsets of the set {1,…,n} and whose edges join pairs of subsets that intersect in fewer than s elements; each edge survives independently of the others with probability p. The independence number of the graph G(n,r,<s) equals Cn−sr−s -- this is the classical Erdos-Ko-Rado theorem. We prove that, for r=r(n)→∞, s=s(n)→∞, s=o(r), r2=o(n) and p≥ 16 sr2ln(n/r)/n, with probability tending to 1 the independence number of the random graph Gp(n,r,<s) also equals Cn−sr−s, i.e., the Erdos-Ko-Rado result is stable under random sparsification of the graph. Thereby, in the range of parameters s→∞, s=o(r), a recent result of Raigorodskii and Karas is strengthened: the lower bound on the probability p that guarantees stability is lowered by a factor of about r/s.
Related
- Independence number, essential connectivity and the distance spectral radius of graphs
- On the Stability of the Independence Number of the Distance Graph G(n,r,<s) for Growing r and s
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- Strong complete immersions in graphs with independence number two
- Connected graphs with equal independence number and radius
BibTeX
@misc{pokhachevskiy2026stability,
title = {{On the Stability of the Independence Number in Random Distance Graphs}},
author = {Vsevolod A. Pokhachevskiy and Andrei Raigorodskii},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08897},
eprint = {2609.08897},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08897},
}
RIS
TY - UNPB
TI - On the Stability of the Independence Number in Random Distance Graphs
AU - Vsevolod A. Pokhachevskiy
AU - Andrei Raigorodskii
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08897
UR - https://arxiv.org/abs/2609.08897
AB - We consider a random subgraph G_p(n,r,<s) of the complete distance graph G(n,r,<s) whose vertices are the r-element subsets of the set {1,…,n} and whose edges join pairs of subsets that intersect in fewer than s elements; each edge survives independently of the others with probability p. The independence number of the graph G(n,r,<s) equals C_n−s^r−s -- this is the classical Erdos-Ko-Rado theorem. We prove that, for r=r(n)→∞, s=s(n)→∞, s=o(r), r^2=o(n) and p≥ 16 sr^2ln(n/r)/n, with probability tending to 1 the independence number of the random graph G_p(n,r,<s) also equals C_n−s^r−s, i.e., the Erdos-Ko-Rado result is stable under random sparsification of the graph. Thereby, in the range of parameters s→∞, s=o(r), a recent result of Raigorodskii and Karas is strengthened: the lower bound on the probability p that guarantees stability is lowered by a factor of about r/s.
ER -