On "stability" in the Erdős-Ko-Rado theorem

Abstract

Denote by $K_p(n,k)$ the random subgraph of the usual Kneser graph $K(n,k)$ in which edges appear independently, each with probability $p$. Answering a question of Bollobás, Narayanan, and Raigorodskii,we show that there is a fixed $p<1$ such that a.s. (i.e., with probability tending to 1 as $k\to \infty$) the maximum independent sets of $K_p(2k+1,k)$ are precisely the sets $\{A\in V(K(2k+1,k)):x\in A\}$ ($x\in [2k+1]$). We also complete the determination of the order of magnitude of the "threshold" for the above property for general $k$ and $n\ge 2k+2$. This is new for $k\sim n/2$, while for smaller $k$ it is a recent result of Das and Tran.

10 pages