On the Stability of the Independence Number in Random Distance Graphs

Source abstract

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$.