Metraipolis › archive › dc_ee1611db4232

On the Stability of the Independence Number in Random Distance Graphs — arXiv:2609.08897

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08897
License (as archived)
CC0-1.0
Archived
2026-10-16T14:35:43.926Z
SHA-256 of the archived text
84724c82786c6b3693e2e080e65d50d3a7cdacfba4d9a2bf285c693215463f3e
Stable URL of this page
https://metraipolis.com/documento/dc_ee1611db4232

How to cite

On the Stability of the Independence Number in Random Distance Graphs — arXiv:2609.08897 — arXiv (en), https://arxiv.org/abs/2609.08897 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ee1611db4232 (Metraipolis archive dc_ee1611db4232, sha256 84724c82786c6b3693e2e080e65d50d3a7cdacfba4d9a2bf285c693215463f3e)
BibTeX
@misc{dcee1611db4232,
  title = {On the Stability of the Independence Number in Random Distance Graphs — arXiv:2609.08897},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08897},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ee1611db4232; sha256 84724c82786c6b3693e2e080e65d50d3a7cdacfba4d9a2bf285c693215463f3e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08897. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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,\dots,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)\to\infty$, $s=s(n)\to\infty$, $s=o(r)$, $r^2=o(n)$ and $p\ge 16\,sr^2\ln(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\to\infty$, $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$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.PR).
Categorie arXiv: Combinatorics (math.CO) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.08897 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:09:59.862Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).