Extremal Combinatorics III: Some Basic Theorems

Posted on September 28, 2008 by Gil Kalai

Shattering

Let us return to extremal problems for families of sets and describe several basic theorems and basic open problems. In the next part we will discuss a nice proof technique called “shifting” or “compression.”

The Sauer-Shelah (-Perles -Vapnik-Chervonenkis) Lemma:

(Here we write $N = \{1,2,\dots,n\}$ .) A family ${\cal F} \subset 2^N$ shatters a set $S \subset N$ if for every $R \subset S$ there is $F \in {\cal F}$ such that $S \cap F=R$ . Note that in order to shatter a set of size $m$ you need at least $2^m$ sets. But how many sets will guarantee that you shatter a set with $m$ elements? The Sauer-Shelah Lemma answers this question!

Theorem (Sauer-Shelah): If $\cal F > {n \choose 0} + {n \choose 1} + \dots + {n \choose k}$ then there exists a set $S$ , $|S|=k+1$ such that $\cal F$ shatters $S$ .

Hmm LaTeX can go wild, let me try that again:

Theorem (Sauer-Shelah): If $|{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k}$ then there exists a set $S$ , $|S|=k+1$ such that $\cal F$ shatters $S$ .

(This is much better.)

The simplest way to prove this theorem is by induction. Here is a variation I just heard from Noga. Proof (a little sketchy): Prove a slightly stronger fact that every family $\cal F$ shatters at least as many sets as $|{\cal F}|$ . Consider the subfamily ${\cal F}_0$ of sets in the family not containing $'1'$ . By induction ${\cal F}_0$ shatters at least as many subsets of $N' = \{2,3, \dots , n\}$ as $|{\cal F}_0|$ . Next consider ${\cal F}_1 =$ $\{S \in {\cal F}: 1 \in S\}$ , and ${\cal F}'_1$ = $\{S \backslash \{1\}:$ $S \in {\cal F}, 1 \in S \}$ . By induction ${\cal F}'_1$ shatters as many subsets of $\{2,3,\dots,n\}$ as its cardinality. The number of subsets of $N'$ shattered by ${\cal F}_0$ and ${\cal F}'_1$ sum up to at least $|{\cal F}_0|$ + $|{\cal F}'_1|$ = $|{\cal F}|$ , and every subset of $N'$ shattered by ${\cal F}'_1$ is shattered by ${\cal F}_1 \subset {\cal F}$ . Sababa? not quite! there may be subsets $R \subset N'$ shattered by both ${\cal F}_0$ and ${\cal F}'_1$ . But note that in this case both $R$ and latex $R \cup \{1\}$ are shattered by $\cal F$ . walla!

OK, let me give a few more words of explanation about the proof. When I say “every family” do I mean “every family that satisfies the condition of the theorem?” (And If I do why can I use induction?) No, i really mean every family. The point is that if every family shatters at least as many sets as its size then a family which satisfies $|{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k}$ shatters more sets than this sum. But then it must shatter a set of size larger than $k$ because there are not enough subsets of the set $\{1,2,\dots,n\}$ of size at most $k$ .

One additional word about the proof. Considering the sets containing ‘1’ and those not containing ‘1’ and then applying an inductive argument which can be simple or extremely complicated, direct or involving several additional methods, is a very basic proof method in extremal set theory.

This theorem can be described as an “eigentheorem” because it is important in many different places. It was mentioned (with an algebraic proof by Frankl and Pach) in Gowers’ blog and also, in another context, in Kowalski’s blog. Sauer proved it in response to a problem of Erdos. Shelah (with Perles) proved it as a useful lemma for Shelah’s theory of stable models. (At some later time, Benjy Weiss asked Perles about such a result in the context of ergodic theory and Perles who forgot that he proved it once proved it again.) Vapnik and Chervonenkis proved it in the context of statistical learning theory. The VC-dimension of a family of sets is the size of the largest set the family shatters. This notion plays an important role in learning theory, statistics and probability theory. There are several applications of the Sauer-Shelah theorem to analysis and to the geometry of Banach spaces, and there are several extensions and refinements.

The Kruskal-Katona Theorem

We let $\bf N$ denote the set of positive integers and let ${{\bf N} \choose {k}}$ = $\{S: S \subset {\bf N}, |S|=k\}$ .

Let ${\cal F}$ be a subset of ${{\bf N} \choose {k}}$ . The Shadow $\partial {\cal F}$ is the set of all (k-1)-subsets of $\bf N$ which are contained in at least one set in $\cal F$ .

We would like to answer the following question. How small can the Shadow of a family of m k-sets be? The precise answer to this question is given by the Kruskal-Katona’s theorem.

First write $m = {{m_k} \choose {k}}$ + ${{m_{k-1}} \choose {k-1}}$ + $\dots$ + ${{m_j} \choose {j}}$ , where $m_k >m_{k-1} > \dots m_j \ge j >0$ .

It is not hard to see that (when k is fixed) there is a unique way to write m in this manner.

(Hint: Choose $m_k$ to be the largest integer $b$ so that ${{b} \choose {k}} \le m$ . With this choice $m -{{m_k} \choose {k}} \le {{m_k-1} \choose {k-1}}$ and you can continue choosing $m_{k-1}, m_{k-2}, \dots$ so that $m_k > m_{k-1} > \dots$ . Any other choice for $m_k$ will fail.)

Kruskal Katona Theorem: Let ${\cal F}$ be a subset of ${{{\bf N}} \choose {k}}$ . Suppose that $|{\cal F}|=m$ . Then

$|\partial {\cal F}| \ge$ ${{m_k} \choose {k-1}}$ + ${{m_{k-1}} \choose {k-2}}$ $+ \dots +$ ${{m_j} \choose {j-1}}$ .

Shadow

The Kruskal-Katona theorem is very basic both in extremal combinatorics and in algebraic combinatorics. An earlier similar theorem about families of multisets (or monomials) was proved by Macaulay in 1927.

The Erdos-Rado Sunflower Theorem

A sunflower (a.k.a. Delta-system) of size $r$ is a family of sets $A_1, A_2, \dots, A_r$ such that every element that belongs to more than oneofthe sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function $f(k,r)$ so that every family $\cal F$ of $k$ -sets with more than $f(k,r)$ members contains a sunflower of size $r$ .

(We denote by $f(k,r)$ the smallest integer that suffices for the assertion of the theorem to be true.)

Proof: Let $\cal F$ be a family of $k$ -sets without a sunflower of size $r$ . Let $A_1, A_2, \dots , A_t$ be a maximum subfamily of pairwise disjoint sets in $\cal F$ . Since a family of pairwise disjoint sets is a sunflower, we must have $t<r$ . Now let $A = \cup_{i=1}^t A_i$ . For every $a \in A$ consider the family ${\cal F}_a = \{ S \backslash \{a\}: S \in {\cal F}, a \in S\}$ . Now, the size of $A$ is at most $(r-1)k$ and the size of each ${\cal F}_a$ is at most $f(k-1,r)$ . (Because a sunflower in ${\cal F}_a$ gives a sunflower in $\cal F$ as well.) We get that $f(k,r) \le (r-1)k f(k-1,r)$ . This gives $f(k,r) \le (r-1)^k \times k!$ . Walla!

The Erdos-Rado Sunflower Conjecture

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that $f(k,r) \le c_r^k$ .

Here, $c_r$ is a constant depending on $r$ . This is most interesting already for $r=3$ .

(Sept 09: The Erdos-Rado sunflower (Delta-system) conjecture was proposed by Tim Gowers, among other problems, for a “polymath project.”)

The Harris-Kleitman theorem

An ideal of sets is a family of sets closed under taking subsets. Ideals are also called, down-families and simplicial complexes. A filter of sets is a family closed under taking supersets.

The Harris-Kleitman Theorem: Let $\cal F$ and ${\cal G}$ be two ideals in $2^A$ , $|A|=n$ . then:

$|{\cal F} \cap {\cal G}|/2^n \ge |{\cal F}|/2^n \cdot |{\cal G}|/2^n.$

This theorem asserts that for random subsets of $2^A$ the events “to be in $\cal F$ ” and “to be in $\cal G$ ” have nonnegative correlation. This can be seen as a first result in a wide and important area of correlation inequalities. The proof is by a rather easy induction.

By considering the complement $\cal H$ of $\cal G$ in $2^A$ we get that the events: “to be in $\cal F$ ” and “to be in $\cal H$ ” have nonpositive correlation, whenever $\cal F$ is an ideal and $\cal H$ is a filter.

Solving Problem II from Lecture 1.

Problem II: What is the largest size of a family $\cal F$ of subsets of $N$ such that for every two sets $S,R$ in $\cal F$ the intersection of $R$ and $S$ is non empty and their union is not $N$ . (here, $N=\{1,2,\dots,n\}$ .)

Answer: $2^{n-2}$ . (This is a theorem by D. J. Kleitman.)

Proof: The family of all sets containing ‘1’ and missing ‘2’ is an example with $2^{n-2}$ sets. To show that there is no larger example, take the family $\cal F$ and turn it to an ideal $\cal I$ by closing it to subsets. This ideal will still satisfy the condition that the union of two sets is not $N$ and therefore ${\cal I} \le 2^{n-1}$ . Now take the family $\cal F$ again and make it a filter $\cal J$ by closing it to supersets. This filter is intersecting (the intersection of two sets belonging to it is not empty) and therefore also $|{\cal J}| \le 2^{n-1}$ . The Harris-Kleitman theorem asserts that the events “a random set belongs to $I$ ” and “a random set belongs to $\cal J$ ” have nonpositive correlation. The probability of a random set to belong to $\cal I$ is at most 1/2; the probability of a random set to belong to $\cal J$ ist also at most 1/2, and, therefore, the probability of a random set to belong to both $\cal I$ and $\cal J$ is at most 1/4. In other words, the number of sets in ${\cal I} \cap {\cal J}$ is at most $2^{n-2}$ . Of course every set in $F$ is both in $\cal I$ and in $\cal J$ Sababa!

The Two Families Theorem

Bollobas’s Two Families theorem is beautiful and useful.

Theorem: Let $A_1,A_2,\dots A_t$ and $B_1,B_2,\dots , B_t$ be two families of sets having the following properties:

1) for every $i$ , $|A_i| \le k$ , and $|B_i| \le \ell$ .

2) For every $i$ $A_i \cap B_i = \emptyset$ ,

3) for every $i \ne j$ , $A_i \cap B_j \ne \emptyset$ .

Then $t \le {{k+\ell} \choose {k}}$ .

Of course, the bound of this theorem is sharp, as seen by taking the $A_i$ s to be all k-subsets of a set with $k+\ell$ elements and letting $B_i$ be the complement of $A_i$ . There is a very nice proof (due to Katona, I think) that is similar to the proofs we saw in part I for Sperner’s theorem and for Erdos-Ko-Rado’s theorem. Here is a sketch:

Proof: You can assume that $|A_i|=k$ and $|B_i|=\ell$ for every $i$ . (Just add fresh new elements to these sets if needed.) Let X be the union of all the $A_i$ s and $B_i$ s. Suppose that $|X|=n$ . Count pairs $(\pi, i)$ where $\pi$ is an ordering of X, and $i$ is an index with the property that all elements of $A_i$ come before all elements of $B_i$ in the ordering. And now note first that the intersection property we described guarantees that for every $\pi$ there is at most one possible $i$ . So the total number of pairs is at most $n!$ . On the other hand for every $i$ the number of $\pi$ for which the elements of $A_i$ come before those of $B_i$ is precisely $k! \times \ell! \times (n-k-\ell)! \times {{n} \choose {k+\ell}}$ . So $t \times k! \times \ell! \times (n-k-\ell)! \times {{n} \choose {k +\ell}} \le n!$ and this gives $t \le {{k+\ell} \choose {k}}$ . Ahla!

Reminder: Arabic words which are part of Hebrew slang: ashkara – for real; sababa – cool, wonderful; walla – true; ahla – great; yalla – hurry up, c’mon, let’s go.

We end this post with two other central open problems in extremal combinatorics.

Chvatal’s conjecture

For a family $F$ of sets and an element $a$ denote by ${\cal F}_a = \{S \in {\cal F}: a \in S\}$ .

Chvatal’s conjecture: Let $\cal F$ be an ideal of sets and let $\cal G$ be an intersecting subfamily, (i.e., for every $S,T \in {\cal G}$ , $S \cap T \ne \emptyset$ ). Then there is an element $a$ so that $|{\cal G}| \le |{\cal F}_a|$ .

There is something in Chvatal’s conjecture that resembles Frankl’s problem from the very first post.

Simonyi’s conjecture

Here is a beautiful conjecture by Gabor Simonyi. Let $\cal A$ , $\cal B$ be two families of subsets of an $n$ -set (a set with n elements). Suppose that the following two conditions hold:

1) For every $A, A' \in {\cal A}$ and $B, B' \in {\cal B}$

$A \backslash B = A' \backslash B'$ implies $A = A'$ .

2) For every $A, A' \in {\cal A}$ and $B, B' \in {\cal B}$

$B \backslash A = B' \backslash A'$ implies $B=B'$ .

Then $|{\cal A}| \times |{\cal B}| \le 2^n$ .

Happy new year

And to all the readers: happy new (Jewish) year!

This entry was posted in Combinatorics, Open problems and tagged Extremal combinatorics, Shana Tova. Bookmark the permalink.

18 Responses to Extremal Combinatorics III: Some Basic Theorems

Pingback: Math and Food Blogs « Dave a.g.p.’s Blog
Pingback: Lovasz’s Two Families Theorem « Combinatorics and more
Pingback: Extremal Combinatorics on Permutations « Combinatorics and more
Pingback: How the g-Conjecture Came About « Combinatorics and more
Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more
Pingback: Analysis of Boolean Functions – week 1 | Combinatorics and more
Pingback: Analysis of Boolean Functions – week 4 | Combinatorics and more
Pingback: Influence, Threshold, and Noise | Combinatorics and more
Pingback: Updates and plans III. | Combinatorics and more
Pingback: Polymath10: The Erdos Rado Delta System Conjecture | Combinatorics and more
Pingback: Polymath10: The Erdos Rado Delta System Conjecture | Combinatorics and more
Seva says:

August 1, 2016 at 9:12 pm

What I never quite understood about the Kruskal-Katona theorem is the ideology behind looking at *uniform* set families. Why this ultimately turns out more useful than considering just *all* families? Is it trivial / easy to determine the smallest possible size of the shadow of a (not necessarily $k$-uniform) set family of given size $m$?

Reply
Pingback: Touching Simplices and Polytopes: Perles’ argument | Combinatorics and more
Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more
Pingback: Extremal Combinatorics V: POSETS | Combinatorics and more
Pingback: Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture | Combinatorics and more
Pingback: Possible future Polymath projects (2009, 2021) | Combinatorics and more
Pingback: L_k 구별을위한 가장 작은 NFA 크기의 경계 작은 비 결정적 - How IT

	My Notices AMS Paper… on The Quantum Computer Puzzle @…
	My Notices AMS Paper… on Random Circuit Sampling: Fouri…
	My Notices AMS Paper… on Photonic Huge Quantum Advantag…
	My Notices AMS Paper… on Ordinary computers can beat Go…
	My Notices AMS Paper… on Amazing: Feng Pan and Pan Zhan…
	Gil Kalai on Three Remarkable Quantum Event…
	Arturo Merino, Torst… on Updates from Cambridge
	ryeguy10 on Updates from Cambridge
	Gil Kalai on Updates from Cambridge
	Gil Kalai on Updates from Cambridge
	Rivki on Updates from Cambridge
	Sandy H on Updates from Cambridge