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| \geq 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,\ldots,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| \neq 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) \leq k \leq 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}| \geq f(n,k,t) - O(\binom{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(\binom{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.

Topics & Concepts