An isoperimetric approach to some Erdos-Ko-Rado type problems

Add to your list(s) Download to your calendar using vCal

• David Ellis (QMUL)
• Tuesday 09 October 2018, 15:00-16:00
• Arts LR2.

If you have a question about this talk, please contact Guillem Perarnau.

An Erdos-Ko-Rado (EKR) problem asks for a determination of the maximum possible size of a family of sets, subject to some intersection requirement on the sets in the family. An EKR ‘stability’ problem asks for a description of the families that satisfy this intersection requirement and moreover have size ‘close’ to the maximum possible size. We make some progress on various EKR problems and EKR stability problems, via a technique based on isoperimetric inequalities for subsets of the hypercube. We substantially improve an old result of Frankl and Furedi on the maximum possible size of the union of a fixed number of intersecting families of k-element subsets of an n-element set, resolving the question for k < (1/2-o(1))n, and we prove an almost-sharp ‘stability’ result on t-intersecting families of k-element sets, strengthening a result of Friedgut. Based on joint work with Nathan Keller (Bar Ilan University) and Noam Lifshitz (Bar Ilan University).

This talk is part of the Combinatorics and Probability Seminar series.

This talk is included in these lists:

• Arts LR2
• Combinatorics and Probability Seminar
• School of Mathematics Events

Note that ex-directory lists are not shown.