Combinatorics Seminar

When: Sunday, December 18, 10am
Where: Schreiber 309
Speaker: David Ellis, Queen Mary University of London
Title: Some applications of the p-biased measure to Erdős-Ko-Rado type problems


If X is a finite set, the p-biased measure on the power-set of X is defined as follows: choose a subset S of X at random by including each element of X independently with probability p. If FF is a family of subsets of X, one can consider the p-biased measure of FF, denoted by \mu_p(FF), as a function of p; if FF is closed under taking supersets, then this function is an increasing function of p. Seminal results of Friedgut and Friedgut-Kalai give criteria for this function to have a "sharp threshold". A careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the p-biased measure - in particular, in the field of Erdős-Ko-Rado type problems, which concern the sizes of families of objects in which any two (or three…) of the objects "agree" or "intersect" in some way. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of {1,2,...,n} has size o(2^n), and a sharp bound on the size of the union of two intersecting families of k-element subsets of {1,2,...,n}, for k≤n/2-o(n). Based on joint work with (subsets of) Nathan Keller, Noam Lifshitz and Bhargav Narayanan.