Removal and Stability for Erd\H{o}s-Ko-Rado

A $k$-uniform family of subsets of $[n]$ is intersecting if it does not contain a disjoint pair of sets. The study of intersecting families is central to extremal set theory, dating back to the seminal Erd\H{o}s-Ko-Rado theorem of 1961 that bounds the size of the largest such families. A recent trend has been to investigate the structure of set families with few disjoint pairs. Friedgut and Regev proved a general removal lemma, showing that when $\gamma n \le k \le (\tfrac12 - \gamma)n$, a set family with few disjoint pairs can be made intersecting by removing few sets. We provide a simple proof of a removal lemma for large families, showing that families of size close to $\mathrm{\ell }\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)$ with relatively few disjoint pairs must be close to a union of $\mathrm{\ell }$ stars. Our lemma holds for a wide range of uniformities; in particular, when $\mathrm{\ell }=1$, the result holds for all $2\le k<\frac{n}{2}$ and provides sharp quantitative estimates. We use this removal lemma to settle a question of Bollob'as, Narayanan and Raigorodskii regarding the independence number of random subgraphs of the Kneser graph $K(n,k)$. The Erd\H{o}s-Ko-Rado theorem shows $\alpha(K(n,k)) = \binom{n-1}{k-1}$\mathrm{.}Forsomeconstant$c > 0$and$k \le cn$, we determine the sharp threshold for when this equality holds for random subgraphs of $K(n,k)$, and provide strong bounds on the critical probability for $k \le \tfrac12 (n-3)$.