**Compression**

We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems.

### The Sauer-Shelah Lemma:

Let . Recall that a family **shatters** a set if for every there is such that .

**Theorem (Sauer-Shelah):** If then there exists a set , , such that shatters .

### Proof by Shifting

I will describe now a proof of the Sauer-Shelah theorem which is not the easiest but still is quite easy and demonstrates an important technique called “shifting” or “compression” (for an application to additive number theory look at this post by Terry Tao).

The idea of shifting is to reduce an extremal problem for a family of sets to the case of families of a special type. In the case of the Sauer-Shelah Theorem we first make a reduction to families which are closed under taking subsets (such families are called “ideals,” “down-sets,” and “simplicial complexes”). Then we prove the theorem for such families.

**Shifting boundaries (a poster of a conference in Manchester Sept 2000)**

### An Analogue: The Isoperimetric Theorem and Steiner Symmetrization

Shifting can be regarded as analogous to the method of symmetrization in geometry which is used mainly in the context of isoperimetric inequalities. The famous isoperimetric theorem asserts that the ball is the set of a given volume with minimal surface area (and also minimal diameter). The symmetrization method for proving it is to repeat an operation which makes the body more and more symmetric, (and in the limit turns it into a ball,) while keeping the volume fixed and not increasing the surface area (or the diameter). Steiner symmetrization is the most famous: Starting with a set , you choose a hyperplane and in every line orthogonal to it, you replace the points in with an interval, symmetric with respect to the hyperplane, whose length is precisely the measure of .

**Steiner symmetrization** (here the hyperplane H is a line denoted by L)

**The shifting operation (for arbitrary families):**

We perform repeatedly the following operation where is an index from 1 to n. We can think about this operation as follows: “Having a set in the family which contains while not having the set **is not good**: in such a case we will replace with “.

Formally we define for , if either

a) or

b) If and .

In the remaining case, i.e., **and** we define

Finally we define = .

Now we need the following basic properties:

1) Starting with a family when we repeat these shifting operations until none of them makes a difference, we reach an ideal .

2) has the same number of sets as .

3) If shatters a set then so does

If we assume these three properties, then in order to prove the Sauer-Shelah theorem we need to prove it just for families that are ideals. But when it comes to ideals, shattering is easy. Every set which belongs to an ideal is shattered by it. (And every set not belonging to the ideal is not shattered by it.) Therefore, if an ideal does not shatter a set of size k+1 it contains only sets of size at most k and the theorem follows.

Properties 1) and 2) are immediate so let us prove property 3).

In fact, something even more general holds: Let’s define the **trace** of on as the family . We denote the trace of on by . The size of the trace of every set does not increase after performing a shifting operation, and in fact

.

**Proof:** To see this, first note that if then the trace of does not change when we shift. Suppose . Suppose further that is in the trace of on . If and with then and therefore . So suppose that .

Now, let’s see. If does not contain and is **not** in the trace of on , and with it must be the case that is not in , but rather is. In this case is in the trace of on . It is left to make sure that is not in the trace of on . But indeed it is not. Otherwise , = where and hence . The survival of in the shifting tells us that = is in but then and this is in contradiction to **not** being in the trace of on . **sababa!**

### The shifting operation (uniform case).

There is a version of the shifting method which works for families of k-sets when k is fixed. Here you shift the set in order to make the elements “as small as possible”. The size of the set is left unchanged. In fact, this is the original form of shifting that Erdos, Ko and Rado used in their original paper. This method was crucial in the solution of the “Erdos-Ko-Rado problem” that we will mention below.

Here is how the shifting works:

Given we start with a family and shift it to a new family . For define if either or or . But if and and then we let .

Finally .

### Properties of shifting (the uniform case):

1) The number of sets in the family remains the same.

2) If is an intersecting family so is In fact more is true. If has the property that among every sets there are two whose intersection has at least elements then this property is preserved under shifting.

3)

4) Starting with a family we can repeat the shifting operation until we end up with a family which remains fixed under all shifting operations . Such a family is called **shifted**.

Property 1 is immediate and property 4 is very easy. Proving properties 2) and 3) requires the type of element-chasing we used above for the relation between shifting and traces. I will not repeat the proofs here.

### Proving Kruskal-Katona.

There are many proofs for the Kruskal-Katona Theorem. Some of the proofs depend on the identity of families for which the bound is tight. These families are **initial families** among subsets of size from the positive integers, with respect to the “reverse lexicographic order”. The **reverse lexicographic order** is ordering the sets lexicographically when each individual set is ordered from its largest element to its smallest.

For example, in the reverese lexicographic order: {2,1} < {3,1} < {3,2} < {4,1} < {4,2} < {4,3} < and {3,2,1} < {4,2,1} < {4,3,2} …

What is an initial set with respect to an order relation on a set ? It is a set of elements such that if then there is no with . (I refer as “families” to “sets of sets”. A set of sets which is initial with respect to a partial order on sets is thus called “an initial family”.)

The proof using shifting is also direct and simple. The proof relies on the most obvious inductive idea: Split your family into two parts: consider sets containing the element ‘1’ and those that do not contain the element ‘1’. (This is the basic inductive step in surprisingly many cases; we saw an argument like this for the Sauer-Shelah Theorem and it works, for example, for proving Harris-Kleitman theorem from the previous lecture.)

On top of this the proof uses the basic recurence relations for binomial coefficients and one additional fact: For a shifted family the shadow of a set not containing the element ‘1’ is already in the shadow of a set containing the element ‘1’.

### Erdos-Ko-Rado’s theorem (revisited).

The proof of Erdos-Ko-Rado’s theorem using shifting (which is the original proof) works like this. **Proof:** You first find a direct proof when n=2k. (There it is easy, since every pair of complementary sets can send only one representative to the intersecting family, and

Hmm, what a, unexpected LaTeX-bug beauty. let’s start from the beginning.

**Proof:** You first find a direct proof when n=2k.(There it is easy, since every pair of complementary sets can send only one representative to the intersecting famiy, and ) Property 2 (with properties 1 and 3) reduces the theorem from general intersecting families to shifted intersecting families. Let be a shifted intersecting family of -subsets of , . We assume that the theorem holds for smaller values of . For such a family , we can apply the basic inductive trick: we consider the family sets in not containing ‘n’, and the family of those sets containing ‘n’ and the family . By induction (without using the assumption that is shifted) we get: . If we could show that is an intersecting family it would follow by the induction hypothesis that = and then = + .

Why is an intersecting family? This is the crux of the matter. Otherwise you would have two sets in which share only the element ‘n’. Aha, but the union of these two sets must miss one of the elements from . But then we can obtain a set by deleting from the element ‘n’ and adding the element ‘‘. The new set must also be in ! (Here we use the fact that is a shifted family.) But is disjoint to which is a contradiction.

**Sababa!**

### The Erdos-Ko-Rado Problem, and the Ahlswede-Khachatrian solution.

What about families of k-subsets from an n-element set such that every two sets in the family have at least two elements in common? or, more generally, every two sets in the family have at least r elements in common.

Here is an example: n=8, k=4, and r=2.

You may think that the best thing to do is to take all 4-subsets containing ‘1’ and ‘2’. There are 15 such sets. But if you take all subsets containing at least 3 elements from {1,2,3,4} you have 17 sets so that every two have at least two elements in common. Erdos, Ko and Rado posed a conjecture for the case n=4r, k=2r. And Peter Frankl posed a conjecture for every n, k, and r. Frankl’s conjecture was settled by Ahlswede and Khachatrian. This was great!

a lecture by Chris Godsil

Pingback: Extremal Combinatorics on Permutations « Combinatorics and more

Pingback: (Eran Nevo) The g-Conjecture I « Combinatorics and more

Pingback: Michael Hay » Blog Archive » Capacity Optimization for Hitachi File and Content Services

Pingback: Leslie Valiant and the PAC Model « Tsourolampis Blog