Computer Science/Discrete Mathematics Seminar I
On the Measure of Interesting Families via Spectral Methods
A family of sets is called intersecting if the intersection of every two sets in the family is non empty. Many of the fundamental theorems in extremal set theory deal with the maximal size of an intersecting family under certain restrictions. A prime example is the Erdos-Ko-Rado theorem that states that if k < n/2 and A is an intersecting family of subsets of {1,2,...,n}, each of size k, then A is no larger than the family of all subsets containing a fixed element. In this talk we take a slightly more analytical slant on such questions, viewing a family of sets as a subset of the discrete cube (viewed as a product measure space), and rather than considering the size of a family we consider its measure. Using eigenvalue techniques and some Fourier analysis one can prove various discrete-measure-theoretic analogies of some basic combinatorial theorems and, actually infer some stronger information concerning uniqueness and stability of the extremal examples in the classical case.