Stability Versions of Erdos-Ko-Rado Type Theorems via Isoperimetry
Seminar
Speaker
Noam Lifshitz (BIU)
Date
03/01/2016 - 15:30 - 14:00Add to Calendar
2016-01-03 14:00:00
2016-01-03 15:30:00
Stability Versions of Erdos-Ko-Rado Type Theorems via Isoperimetry
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.
Building 216, Room 201
אוניברסיטת בר-אילן - Department of Mathematics
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
Place
Building 216, Room 201
Abstract
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.
Last Updated Date : 28/12/2015
