On the Stability of the Independence Number of the Distance Graph G(n,r,<s) for Growing r and s

@misc{pokhachevskiy2026stability,
  title = {{On the Stability of the Independence Number of the Distance Graph G(n,r,<s) for Growing r and s}},
  author = {Vsevolod A. Pokhachevskiy and Andrei Raigorodskii},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16955},
  eprint = {2610.16955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16955},
}

TY  - UNPB
TI  - On the Stability of the Independence Number of the Distance Graph G(n,r,<s) for Growing r and s
AU  - Vsevolod A. Pokhachevskiy
AU  - Andrei Raigorodskii
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16955
UR  - https://arxiv.org/abs/2610.16955
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 stability of the Erdos-Ko-Rado theorem is the event that the independence number of the random subgraph equals that of the original graph, N = C_{n-s}^{r-s}. For fixed r and s, two-sided bounds for the critical probability, whose ratio depends on r and s, were obtained by P. A. Ogarok and A. M. Raigorodskii. In this paper we establish the order of the critical probability for growing r=r(n) and s=s(n): if min{C_r^s r^2, s r^3} = o(n), then the upper and lower bounds differ only by an absolute constant factor. The proof is elementary; only one of the two branches of the growth condition uses the complete nontrivial-intersection theorem of Ahlswede-Khachatrian.
ER  -