Home page of the course.

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.

### Like this:

Like Loading...

*Related*

Pingback: Analysis of Boolean functions – week 2 | Combinatorics and more