REU 2005 · Potpourri · Lecture 2

Instructor: László Babai Scribe: N. Raghunathan July 20, 2005. Last updated July 25, 2005

2 Sperner’s Theorem and Bollobás’ Inequality

2.1 Sperner’s Theorem

Definition 2.1 (Sperner Family). Let F = {A_{1}, A_{2}, …, A_{m}} be a family of subsets of H := {1, 2, …, n}. F is called a Sperner Family if ∀i ≠ j, A_{i} ⊄ A_{j}. Example 2.2 (Singletons). For example the family of singletons F = {{1}, {2}, …, {n}} is a Sperner Family. In fact it is a is maximal Sperner Family. By maximal we mean that we cannot add another set and keep the family Sperner. Definition 2.3 (k-uniform). A family of subsets F = {A_{1}, A_{2}, …, A_{m}} of H = {1, 2, …, n} is called a k-uniform family if ∀j, |A_{j}| = k. Example 2.4 (k-subsets). If X =:= \{1, 2, …, n\}, let \binom{X}{k} := \{A | A ⊂ X, |A| = k\}. That is \binom{X}{k} is set of all subsets of X os size k. For all k, the family \binom{X}{k} is a maximal Sperner family. Note also that |\binom{X}{k}| = \binom{n}{k}.

Notice that \binom{H}{k} is a k-uniform family. Question 2.5. What is the maximum size of a Sperner Family?

For k = ⌊\frac{n}{2}⌋, the family \binom{H}{⌊\frac{n}{2}⌋} is \binom{n}{⌊\frac{n}{2}⌋}. Sperner in 1928 proved that every Sperner family has size at most \binom{n}{⌊\frac{n}{2}⌋}. Theorem 2.6 (Sperner’s Theorem). Let A_{1}, ⋯, A_{m} be a Sperner family of subsets of a set of n elements. Then

m ≤ \binom{n}{⌊\frac{n}{2}⌋}

.

We need some notions from finite probability spaces before we get to the proof.

2.2 Crash Course on Probability

Definition 2.7. A finite probability space is a non-empty finite set Ω together with a function Pr : Ω → ℝ such that

1. (∀x ∈ Ω)(Pr(x) > 0)

2. ∑_{x∈Ω} Pr(x) = 1

The set Ω is the sample space and the function Pr is the probability distribution. The elements ω are called atomic events or elementary events. An event is a subset of Ω. For A ⊆ Ω, we define the probability of A to be Pr(A) := ∑_{ω∈A} Pr(A): In particular, for atomic events we have Pr({ω}) = Pr(ω); and Pr(∅) = 0, Pr(Ω) = 1.

The uniform distribution over the sample space Ω is defined by setting Pr(ω) = 1/|Ω| for every ω ∈ Ω.

Exercise 2.8 (Union Bound). Let (Ω, Pr) be a probability space and A_{1}, A_{2}, …, A_{m} be events. then

Pr(⋃_{i=1}^{m} A_{i} ≤ ∑_{i=1}^{m} Pr(A_{i})

Definition 2.9 (Random Variable). A random variable is a function X : Ω → ℝ.

We say that X is constant if X(ω) takes the same value for all ω ∈ Ω.

Definition 2.10. The expected value of a random variable X is E(X) = ∑_{ω∈Ω} X(ω)Pr(Ω).

Exercise 2.11. min X ≤ E(X) ≤ max X

Exercise 2.12 (Linearity of Expectation). If X_{1}, X_{2}, …, X_{k} be random variables. Prove that

E(X_{1} + ⋯ + X_{k}) = ∑_{i=1}^{k} E(X_{i})

Definition 2.13. The indicator variable of an event A ⊂ Ω is the function ϑ : Ω → {0, 1} given by

ϑ_{A}(ω) = \{ \begin{matrix}1 & for x ∈ A \\ 0 & for x ∉ A \end{matrix}

Exercise 2.14. The expected value of an indicator variable ϑ_{A} is E(ϑ_{A}) = Pr(A).

Example 2.15. A club with 2005 members distributes membership cards numbered 1 through 2005 to its members at random. Members whose card number happens to coincide with their year of birth receive a prize. Determine the expected number of lucky members. Surprisingly the answer will not depend on the age distribution of the club members.

Proof. First we observe that we have the unifrom distribution over a sample space of size 2005!. Let X be number of lucky members if the membership cards are distributed at random. Define the indicator variables

ϑ_{i} = \{ \begin{matrix}1 & if the i^{th} (in alphabetical order) member is lucky \\ 0 & if the i^{th} member is not lucky \end{matrix}

Notice that

X = ϑ_{1} + ϑ_{2} + … + ϑ_{2005}.

Hence

E(ψ) = E(ϑ_{1}) + E(ϑ_{2}) + … + E(ϑ_{2005}).

But E(ϑ_{i}) = Pr(i^{th} member is lucky) = \frac{1}{2005} since the i^{th} has equal chance of getting any card. Hence E(X) = 1.

2.3 Proof of Sperner’s Theorem

Now we prove the Sperner’s Theorem. The proof we present is due to Lubell (1966). Our proof is through a result customarily referred to as the LYM inequality (L=Lubell, Y= Yamamoto,M=Meshalkin). We call it BLYM-inequality to honor Bollobás who produced a more general inequality earlier(see below).

Theorem 2.16 (BLYM Inequality). If F = {A_{1}, A_{2}, …, A_{m}} is a Sperner family of X = {1, 2 …, n}, then

∑_{i=1}^{m} \frac{1}{\binom{n}{|A_{i}|}} ≤ 1.

Proof of Sperner’s Theorem using (B)LYM inequality: Since for all 1 ≤ i ≤ m,

\binom{n}{|A_{i}|} ≤ \binom{n}{⌊\frac{n}{2}⌋},

we get that

1 ≥ ∑_{i=1}^{m} \frac{1}{\binom{n}{|A_{i}|}} ≥ ∑_{i=1}^{m} \frac{1}{\binom{n}{⌊\frac{n}{2}⌋}} = \frac{m}{\binom{n}{⌊\frac{n}{2}⌋}}

Before we prove the LYM-inequality we need the notion of chains.

Definition 2.17 (Chain of subsets). A family of subsets B = {B_{1}, B_{2} …, B_{m}} is called a chain if ∀(i, j)(B_{i} ⊆ B_{j} or B_{j} ⊆ B_{i}). A maximal chain is a chain of distinct subsets which cannot be expanded by adding another subset. Maximal chains increase in increments of 1.

There is a natural one-to-one correspondence between the set of permutations of X and the set of maximal chains over X. Given a permutation σ : X → X, the chain defined by B_{0} = ∅, B_{i} = {σ(1), σ(2), …, σ(i)} is maximal. It is easy to see that this function is one-to-one. Proof of Theorem 2.16: This proof technique is called the Lubell’s permutation method. Consider a random maximal chain of subsets of X

B = {B_{0}, …, B_{n}}

(By random we mean that the sample space is the set of all maximal chains and the probability distribution is uniform). Define the random variable X as

X = |F ∩ B|

Notice that X ≤ 1. This is because otherwise there are two sets A_{i} and A_{j} which occur in both F and B but these two requirements are contradictory (one requires them to be incomparable and the other requires them to comparable.) Hence

E(X) ≤ 1.

Now define the indicator variables ϑ_{i} as

ϑ_{i} = \{ \begin{matrix}1 & if A_{i} ∈ B \\ 0 & if A_{i} ∉ B \end{matrix} .

Notice that X = ϑ_{1} + ϑ_{2} + ⋯ + ϑ_{m}. Hence E(X) = E(ϑ_{1}) + E(ϑ_{2}) + ⋯ + E(ϑ_{m}).

E(ϑ_{i}) = Pr(A_{i} ∈ B)  (2.1)
= \frac{1}{\binom{n}{|A_{i}|}}.  (2.2)

The reason of equation 2.1 is the following. Let k = |A_{i}|. Then the set B_{k} ∈ B can be chose in \binom{n}{k} ways, and all have the equal probability. So Pr(B_{k} = A_{i}) = \frac{1}{\binom{n}{|A_{i}|}}.

2.4 Bollobás’s Inequality

We had seen the following version of the Bollobás’s theorem earlier

Theorem 2.18. [Bollobás’s inequality, uniform version] If F = {A_{1}, A_{2}, …, A_{m}} is a runiform family and G = {B_{1}, B_{2}, …, B_{m}} is a s-uniform family such that (∀i)(A_{i} ∩ B_{i} = ∅) and (∀i ≠ j)(A_{i} ∩ B_{j} ≠ ∅) then m ≤ \binom{r+s}{r}.

Bollobás’s main theorem refers to pairs of not necessarily uniform set systems.

Theorem 2.19 (Bollobás’ inequality, general case). If F = {A_{1}, A_{2}, …, A_{m}} and G = {B_{1}, B_{2}, …, B_{m}} are two families such that ∀(i)(A_{i} ∩B_{i} = ∅) and ∀(i ≠ j)(A_{i} ∩B_{j} ≠ ∅) then

∑_{i=1}^{m} \frac{1}{\binom{|A_{i}|+|B_{i}|}{|A_{i}|}} ≤ 1

Exercise 2.20. Prove Theorem 2.18 using Theorem 2.19

Exercise 2.21. Prove that Bollobás’s inequality (Theorem 2.19) implies the BLYM inequality.

Exercise 2.22. Generalize Lubell’s proof to prove Bollobás’s theorem(Theorem refthm-boll)

The following strengthening of the uniform version of Bollobás’s theorem called the Skew Bollobás theorem was proved by Lovász.

Theorem 2.23 ((“Skew Bollobás Theorem”)Lovász). If F = {A_{1}, A_{2}, …, A_{m}} is a r-uniform family and G = {B_{1}, B_{2}, …, B_{m}} is a s-uniform family such that (∀i)(A_{i}∩B_{i} = ∅) and (∀i < j)(A_{i} ∩ B_{j} ≠ ∅) then m ≤ \binom{r+s}{r}.

Note that we dropped nearly half the constraints: no assumption is made on A_{i} ∩ B_{j} if i > j

Exercise** 2.24. Prove the Skew Bollobás Theorem. (Hint: Linear algebra method. determinants.)