Stability Versions of Erdos-Ko-Rado Type Theorems via Isoperimetry
Noam Lifshitz (BIU)
03/01/2016 - 15:30 - 14:00
Building 216, Room 201
Erdos-Ko-Rado (EKR) type theorems yield upper bounds on the size of set families under various intersection requirements on the elements. Stability versions of such theorems assert that if the size of a family is close to the maximum possible then the family itself must be close (in appropriate sense) to a maximum family.
In this talk we present an approach to stability versions of EKR-type
theorems through 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 (for k < n/(t+1)),
and to show that, somewhat surprisingly, both theorems hold when the "intersection"
requirement is replaced by a much weaker requirement.
Furthermore, we obtain stability versions of several recent EKR-type results, including
Frankl's proof of the Erdos matching conjecture for n>(2s+1)k-s.
Joint work with David Ellis and Nathan Keller.
תאריך עדכון אחרון : 28/12/2015