Removal and Stability for Erdős-Ko-Rado

Abstract

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ő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 ${\hat{I}}^{3}n\le k\le (\frac{1}{2}-{\hat{I}}^3)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 $\ell \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ with relatively few disjoint pairs must be close to a union of $\ell$ stars. Our lemma holds for a wide range of uniformities; in particular, when $\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ás, Narayanan and Raigorodskii regarding the independence number of random subgraphs of the Kneser graph $K(n,k)$. The Erdős-Ko-Rado theorem shows $\hat{I}\pm (K(n,k))=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. For some constant $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 \frac{1}{2}(n-3)$.

13 pages; minor changes made following referee feedback