Combinatorics (Fall 2010)/Extremal set theory II

From EtoneWiki
Jump to: navigation, search

Sauer's lemma and VC-dimension

Shattering and the VC-dimension

Definition (shatter)
Let be set family and let be a subset. The trace of on , denoted is defined as
We say that shatters if , i.e. for all , there exists an such that .

The VC dimension is defined by the power of a family to shatter a set.

Definition (VC-dimension)
The Vapnik–Chervonenkis dimension (VC-dimension) of a set family , denoted , is the size of the largest shattered by .

It is a core concept in computational learning theory.

Each subset can be equivalently represented by its characteristic function , such that for each ,

Then a set family corresponds to a collection of boolean functions , which is a subset of all Boolean functions in the form . We wonder on how large a subdomain , includes all the mappings . The largest size of such subdomain is the VC-dimension. It measures how complicated a collection of boolean functions (or equivalently a set family) is.

Sauer's Lemma

The definition of the VC-dimension involves enumerating all subsets, thus is difficult to analyze in general. The following famous result state a very simple sufficient condition to lower bound the VC-dimension, regarding only the size of the family. The lemma is due to Sauer, and independently due to Shelah and Perles. A slightly weaker version is found by Vapnik and Chervonenkis, who use the framework to develop a theory of classifications.

Sauer's Lemma (Sauer; Shelah-Perles; Vapnik-Chervonenkis)
Let where . If , then there exists an such that shatters .

In other words, for any set family with , its VC-dimension .

Hereditary family

We note the Sauer's lemma is especially easy to prove for a special type of set families, called the hereditary families.

Definition (hereditary family)
A set system is said to be hereditary (also called an ideal or an abstract simplicial complex), if
implies .

In other words, for a hereditary family , if , then all subsets of are also in . An immediate consequence is the following proposition.

Let be a hereditary family. If then shatters .

Therefore, it is very easy to prove the Sauer's lemma for hereditary families:

For , , if is hereditary and then there exists an such that shatters .

Since is hereditary, we only need to show that there exists an of size , which must be true, because if all members of are of sizes , then , a contradiction.

To prove the Sauer's lemma for general non-hereditary families, we can use some way to reduce arbitrary families to hereditary families. Here we apply the shifting technique to achieve this.


Note that we work on , instead of like in the Erdős–Ko–Rado theorem, so we do not need to preserve the size of member sets. Instead, we need to reduce an arbitrary family to a hereditary one, thus we use a shift operator which replaces a member set by a subset of it.

Definition (down-shifts)
Assume , and . Define the down-shift operator as follows:
  • for each , let
  • let .

Repeatedly applying to for all , due to the finiteness, eventually is not changed by any . We call such a family down-shifted. A family is down-shifted if and only if for all . It is then easy to see that a down-shifted must be hereditary.

If is down-shifted, then is hereditary.

In order to use down-shift to prove the Sauer's lemma, we need to make sure that down-shift does not decrease and does not increase the VC-dimension .

  1. ;
  2. , thus if shatters an , so does .

(1) is immediate. To prove (2), it is sufficient to prove that and then apply (1).


Proof of Sauer's lemma

Now we can prove the Sauer's lemma for arbitrary .

For any , repeatedly apply for all till the family is down-shifted, which is denoted by . We have proved that and is hereditary, thus as argued before, here exists an of size shattered by . By the above proposition, , thus also shatters . The lemma is proved.

The Kruskal–Katona Theorem

The shadow of a set system , denoted , consists of all sets which can be obtained by removing an element from a set in .

Let . The shadow of is defined to be

The shadow contains rich information about the set system. An extremal question is: for a system of fixed number of -sets, how small can its shadow be? The Kruskal–Katona theorem gives an answer to this question.

To state the result of the Kruskal–Katona theorem, we need to introduce the concepts of the -cascade representation of numbers and the colex order of sets.

-cascade representation of a number

Given positive integers and , there exists a unique representation of in the form
where .
This representation of is called a -cascade (or a -binomial) representation of .

In fact, the -cascade representation of an can be found by the following simple greedy algorithm:

while () do
    let  be the largest integer for which 

We then show that the above algorithm constructs a sequence with .

Suppose the current and the current . To see that , we suppose otherwise . Then

contradicting the maximality of . Therefore, .

The algorithm continues reducing to smaller nonnegative values, and eventually reaches a stage where the choice of for some where equals the current ; or gets right down to choosing as the integer such that equals the current .

Therefore, and .

The uniqueness of the -cascade representation follows by the induction on .

When , has a unique -cascade representation .

For general , suppose that every nonnegative integer has a unique -cascade representation.

Suppose then that has two -cascade representations:


We then show that it must hold that . If , WLOG, suppose that . We obtain

where the last equation is got by repeatedly applying the identity


We then obtain


which is a contradiction. Therefore, , and by the induction hypothesis, the remaining value has a unique -cascade representation, so for all .

Co-lexicographic order of subsets

The co-lexicographic order of sets plays a particularly important role in the investigation of the size of the shadow of a system of -sets.

The co-lexicographic (colex) order (also called the reverse lexicographic order) of sets is defined as follows: for any , ,
if .

We can sort sets in colex order by first writing each set as a tuple, whose elements are in decreasing order, and then sorting the tuples in the lexicographic order of tuples.

For example, in colex order is


We find that the first sets in this order for , form precisely . And if we write the colex order of , the above colex order of appears as a prefix of that order. Elaborating on this, we have:

Let be the first sets in the colex order of . Then
that is, the first sets in the colex order of all -sets of natural numbers is precisely .

This proposition says that the sets in is highly overlapped, which suggests that may have small shadow. The size of the shadow of is closely related to the -cascade representation of .

Suppose the -cascade representation of is

Given and its -cascade representation , the is constructed as:

  • all sets in ;
  • all sets in , unioned with ;
  • all sets in , unioned with .

The shadow is the collection of all -sets contained by the above sets, which are

  • all sets in ;
  • all sets in , unioned with ;
  • all sets in , unioned with .



The Kruskal–Katona theorem

The Kruskal–Katona theorem states that among all systems of -sets, , i.e., the first -sets in the colex order, has the smallest shadow.

The theorem is proved independently by Joseph Kruskal in 1963 and G.O.H. Katona in 1966, and is a fundamental result in finite set theory and combinatorial topology.

Theorem (Kruskal 1963, Katona 1966)
Let with , and suppose that
where . Then

The -vector of a set system is a vector where


i.e., the -vector gives the number of member sets of each size.

In a hereditary family (also called an abstract simplicial complex), is formed by the shadow of as well as some additional -sets introduced in this level. The Kruskal-Katona theorem gives a lower bound on , given the .

The original proof of the theorem is rather complicated. In the following years, several different proofs were discovered. Here we present a proof dueto Frankl by the shifting technique.

Frankl's shifting proof of Kruskal-Katonal theorem (Frankl 1984)

We take the classic -shift operator defined in the original proof of the Erdős-Ko-Rado theorem.

Definition (-shift)
Assume , and . Define the -shift as an operator on as follows:
  • for each , write , and let
  • let .

It is immediate that shifting does not change the size of the set or the size of the system, i.e., and . And due to the finiteness, repeatedly applying -shifts for any , eventually does not changing any more. We called such an with for any shifted.

In order to make the shifting technique work for shadows, we have to prove that shifting does not increase the size of the shadow.


We abuse the notation and let if is a set instead of a set system.

It is sufficient to show that for any , .


An immediate corollary of the above proposition is that the -shifts for any do not increase the size of the shadow.


By the above proposition, , and we know that does not change the cardinality of a set family, that is, , therefore .

Proof of Kruskal-Katona theorem

We know that shifts never enlarge the shadow, thus it is sufficient to prove the theorem for shifted . We then assume is shifted.

Apply induction on and for given on . The theorem holds trivially for the case that and is arbitrary.



And let .

Clearly , , and


Our induction is based on the following observation regarding the size of the shadow.

Lemma 1

Obviously and .

The union is taken over two disjoint families. Therefore,


The following property of shifted is essential for our proof.

Lemma 2
For shifted , it holds that .

If then for some so that, since is shifted, applying the -shift , , thus, .

We then bound the size of as:

Lemma 3
If is shifted, then

By contradiction, assume that


Then by , it holds that

so that, by the induction hypothesis,


On the other hand, by Lemma 2, . Thus , a contradiction.

Now we officially apply the induction. By Lemma 1,


Note that , and due to Lemma 3,


thus by the induction hypothesis,


Combining them together, we have

Shadows of specific sizes

The definition of shadow can be generalized to the subsets of any size.

The -shadow of is defined as

And the general version of the Kruskal-Katona theorem can be deduced.

Kruskal-Katona Theorem (general version)
Let with , and suppose that
where . Then for all , ,

Note that for ,


The theorem follows by repeatedly applying the Kruskal-Katona theorem for .

The Erdős–Ko–Rado theorem, revisited

To demonstrate the power of the Krulskal-Katona theorem, we show that it actually includes the Erdős–Ko–Rado theorem as a special case. The following elegant proof of the Erdős–Ko–Rado theorem is due to Daykin and Clements independently.

Erdős–Ko–Rado Theorem
Let where and . If for any , then
Proof by the Kruskal-Katona theorem
(Daykin 1974, Clements 1976)

By contradiction, suppose that .

We define the dual system

, where .

For any , the condition is equivalent to , so and are disjoint, thus


Clearly, and


By the Kruskal-Katona theorem, .


a contradiction.