Extremal Combinatorics III: Some Basic Theorems

.

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.

http://www.web-enz.co.nz/sunflower.htm

(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_is 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_is and B_is. 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!

About these ads
This entry was posted in Combinatorics, Open problems and tagged , . Bookmark the permalink.

7 Responses to Extremal Combinatorics III: Some Basic Theorems

  1. Pingback: Math and Food Blogs « Dave a.g.p.’s Blog

  2. Pingback: Lovasz’s Two Families Theorem « Combinatorics and more

  3. Pingback: Extremal Combinatorics on Permutations « Combinatorics and more

  4. Pingback: How the g-Conjecture Came About « Combinatorics and more

  5. Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more

  6. Pingback: Analysis of Boolean Functions – week 1 | Combinatorics and more

  7. Pingback: Analysis of Boolean Functions – week 4 | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s