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
Abstract:
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.