Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós

Abstract

A family $\mathcal{F}$ of sets is said to be t-intersecting if $|A\cap B|\ge t$ for any $A,B\in \mathcal{F}$. The seminal Complete Intersection Theorem of Ahlswede and Khachatrian (1997) gives the maximal size $f(n,k,t)$ of a $t$-intersecting family of $k$-element subsets of $[n]=\{1,\dots ,n\}$, together with a characterisation of the extremal families, solving a longstanding problem of Frankl. The forbidden intersection problem, posed by Erdős and Sós in 1971, asks for a determination of the maximal size $g(n,k,t)$ of a family $\mathcal{F}$ of $k$-element subsets of $[n]$ such that $|A\cap B|\ne t-1$ for any $A,B\in \mathcal{F}$. In this paper, we show that for any fixed $t\in \mathbb{N}$, if $o(n)\le k\le n/2-o(n)$, then $g(n,k,t)=f(n,k,t)$. In combination with prior results, this solves the problem of Erdős and Sós for any constant $t$, except for the ranges $n/2-o(n)<k<n/2+t/2$ and $k<2t$. One key ingredient of the proof is the following sharp ‘stability’ result for the Complete Intersection Theorem: if $k/n$ is bounded away from $0$ and $1/2$, and $\mathcal{F}$ is a $t$-intersecting family of $k$-element subsets of $[n]$ such that $|\mathcal{F}|\ge f(n,k,t)-O((\genfrac{}{}{0ex}{}{n-d}{k}))$, then there exists a family $\mathcal{G}$ such that $\mathcal{G}$ is extremal for the Complete Intersection Theorem, and $|\mathcal{F}\setminus \mathcal{G}|=O((\genfrac{}{}{0ex}{}{n-d}{k-d}))$. This proves a conjecture of Friedgut (2008). We prove the result by combining classical ‘shifting’ arguments with a ‘bootstrapping’ method based upon an isoperimetric inequality. Another key ingredient is a ‘weak regularity lemma’ for families of $k$-element subsets of $[n]$, where $k/n$ is bounded away from 0 and 1. This states that any such family $\mathcal{F}$ is approximately contained within a ‘junta’ such that the restriction of $\mathcal{F}$ to each subcube determined by the junta is ‘pseudorandom’ in a certain sense.