In the first lecture I defined the discrete n-dimensional cube and Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.
1) The largest possible intersecting family of subsets of [n];
2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;
3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;
4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;
5) Erdos-Ko-Rado Theorem.
Exercise: Prove one of the following
a) The Harris-Kleitman’s inequality
b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most sets.
More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)
I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.
More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial: Collective coin flipping, M. Ben-Or and N. Linial, in “Randomness and Computation” (S. Micali ed.) Academic Press, New York, 1989, pp. 91-115.
Pingback: Analysis of Boolean functions – week 2 | Combinatorics and more