Sharp threshold for the Erdős-Ko-Rado theorem

Abstract

For positive integers $n$ and $k$ with $n\ge 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots ,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. The independent sets of $K(n,k)$ are $k$-uniform intersecting families, and hence the maximum size independent sets are given by the Erdős-Ko-Rado Theorem. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollobás, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. For $n=2k+1$, we prove a hitting time result, which gives a sharp threshold for this problem at $p=3/4$. Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all $n>2k+1$.

27 pages; slightly revised with new references; updated funding information; to appear in Random Structures & Algorithms