{"id":"arxiv/2609.08897","url":"https://arxiv.org/abs/2609.08897","tags":["math.CO","math.PR"],"score":0,"title":"On the Stability of the Independence Number in Random Distance Graphs","domain":"math.CO","source":"arxiv","authors":["Vsevolod A. Pokhachevskiy","Andrei Raigorodskii"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}