Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdos and Sos

A family F of sets is said to be t-intersecting if ∣A∩B∣≥t for any A,B∈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,…,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 F of k-element subsets of [n] such that ∣A∩B∣ ≠ t−1 for any A,B∈F. In this paper, we show that for any fixed t∈N, if o(n)≤k≤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 F is a t-intersecting family of k-element subsets of [n] such that ∣F∣≥f(n,k,t)−O((k; n−d​)), then there exists a family G such that G is extremal for the Complete Intersection Theorem, and ∣F∖G∣=O((k−d; n−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 F is approximately contained within a ‘junta’ such that the restriction of F to each subcube determined by the junta is ‘pseudorandom’ in a certain sense.