A tight stability version of the Complete Intersection Theorem

Nathan Keller, Noam Lifshitz

Published 2016-04-20Version 1

A set family F is said to be t-intersecting if any two sets in F share at least t elements. The Complete Intersection Theorem of Ahlswede and Khachatrian (1997) determines the maximal size f(n,k,t) of a t-intersecting family of k-element subsets of {1,2,...,n}, and gives a full characterisation of the extremal families. In this paper, we prove the following `stability version' of the theorem: if k/n is bounded away from 0 and 1/2, and F is a t-intersecting family of k-element subsets of {1,2,...,n} such that $|F| \geq f(n,k,t) - O \binom{n-d}{k}$, then there exists an extremal family G such that $|F \setminus G| = O \binom{n-d}{k-d}$. For fixed t, this assertion is tight up to a constant factor. This proves a conjecture of Friedgut from 2008. Our proof combines classical shifting arguments with a `bootstrapping' method based upon an isoperimetric argument.