Stability versions of Erdős-Ko-Rado type theorems, via isoperimetry

David Ellis, Nathan Keller, Noam Lifshitz

Published 2016-04-07Version 1

Erd\H{o}s-Ko-Rado (EKR) type theorems give upper bounds on the sizes of families of sets, under various intersection requirements on the sets in the family. `Stability' versions of such theorems assert that if the size of a family is close to the maximum possible size, then the family itself must be close (in an appropriate sense) to a maximum-sized family. In this paper, we present an approach to obtaining stability versions of EKR-type theorems, via isoperimetric inequalities for subsets of the hypercube. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on $t$-intersecting families of $k$-element subsets of $\{1,2,\ldots,n\}$ (for $k < \frac{n}{t+1}$), and to show that, somewhat surprisingly, the results hold when the `intersection' requirement is replaced by a much weaker requirement. We also obtain stability versions of several more recent EKR-type results, including Frankl's recent result on the Erd\H{o}s matching conjecture.