Extremal Combinatorics IV: Shifting

Compression

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

The Sauer-Shelah Lemma:

Let $N=\{1,2,\dots,n\}$ . Recall that a family ${\cal F} \subset 2^N$ shatters a set $S \subset N$ if for every $R \subset S$ there is $T \in {\cal F}$ such that $S \cap T=R$ .

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$ .

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 $\cal F$ 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 $K$ , you choose a hyperplane $H$ and in every line $\ell$ orthogonal to it, you replace the points in $K \cap \ell$ with an interval, symmetric with respect to the hyperplane, whose length is precisely the measure of $K \cap \ell$ .

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

The shifting operation (for arbitrary families):

We perform repeatedly the following operation ${\cal F} \to s_k( {\cal F}),$ where $k$ is an index from 1 to n. We can think about this operation as follows: “Having a set $S$ in the family which contains $k$ while not having the set $S \backslash k$ is not good: in such a case we will replace $S$ with $S \backslash k$ “.

Formally we define for $S \in {\cal F}$ , $s_k( S)=S$ if either

a) $k \notin S$ or

b) If $k \in S$ and $(S \backslash \{k\}) \in {\cal F}$ .

In the remaining case, i.e., $k \in S$ and $(S \backslash \{k\}) \not \in {\cal F}$ we define $s_k( S)=(S \backslash \{k\} ).$

Finally we define $s_k({\cal F})$ = $\{ s_k(S): S \in {\cal F} \}$ .

Now we need the following basic properties:

1) Starting with a family $\cal F$ when we repeat these shifting operations until none of them makes a difference, we reach an ideal $S({\cal F})$ .

2) $S({\cal F})$ has the same number of sets as $\cal F$ .

3) If $S({\cal F})$ shatters a set $A$ then so does $\cal F$

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 $\cal F$ on $S$ as the family $\{T \cap S: T \in {\cal F}\}$ . We denote the trace of $\cal F$ on $S$ by $Tr_{\cal F}(S)$ . The size of the trace of every set does not increase after performing a shifting operation, and in fact

$Tr_{s_i ({\cal F})}(S) \subset s_i(Tr _{\cal F}(S))$ .

Proof: To see this, first note that if $i \notin S$ then the trace of $S$ does not change when we shift. Suppose $i \in S$ . Suppose further that $R$ is in the trace of $s_i ({\cal F})$ on $S$ . If $i \in R$ and $R = S \cap T$ with $T \in s_i({\cal F})$ then $i \in T$ and therefore $T \in {\cal F}$ . So suppose that $i \notin R$ .

Now, let’s see. If $R$ does not contain $i$ and $R$ is not in the trace of $\cal F$ on $S$ , and $R= S \cap T$ with $T \in s_i({\cal F})$ it must be the case that $T$ is not in $\cal F$ , but rather $T \cup \{i\}$ is. In this case $R'=R \cup \{i\}$ is in the trace of $\cal F$ on $S$ . It is left to make sure that $R \cup \{i\}$ is not in the trace of $s_i({\cal F})$ on $S$ . But indeed it is not. Otherwise , $R \cup \{ i \}$ = $S \cap T'$ where $T' \in s_i({\cal F})$ and hence $T' \in {\cal F}$ . The survival of $T'$ in the shifting tells us that $T'$ = $T \backslash \{ i \}$ is in $\cal F$ but then $R = T' \cap S$ and this is in contradiction to $R$ not being in the trace of $\cal F$ on $S$ . 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 $i<j$ we start with a family $\cal F$ and shift it to a new family $s_{i,j}({\cal F})$ . For $S \in {\cal F}$ define $s_{i,j}(S)=S$ if either $i \in S$ or $j \not \in S$ or $S \backslash \{j\} \cup \{i\} \in {\cal F}$ . But if $j \in S$ and $i \not \in S$ and $S \backslash \{j\} \cup \{i\} \not \in {\cal F}$ then we let $s_{i,j}(S)=$ $S \backslash \{j\} \cup \{i\}$ .

Finally $s_{i,j}({\cal F}) = \{ s_{i,j} (S): S \in {\cal F}\}$ .

Properties of shifting (the uniform case):

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

2) If $\cal F$ is an intersecting family so is $s_{i,j}({\cal F}).$ In fact more is true. If $\cal F$ has the property that among every $r$ sets there are two whose intersection has at least $\ell$ elements then this property is preserved under shifting.

3) $\partial (s_{i,j}({\cal F})) \subset s_{i,j} (\partial ({\cal F}))$

4) Starting with a family $\cal F$ we can repeat the shifting operation until we end up with a family which remains fixed under all shifting operations $s_{i,j}$ . 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 $k$ 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 $X$ ? It is a set $A$ of elements such that if $b \notin A$ then there is no $a \in A$ with $b<a$ . (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 $1/2 {{2k} \choose {k}} = {{2k-1} \choose {k-1}}.) Property 2 (with properties 1 and 3) reduces the theorem from general intersecting families to shifted intersecting families.$

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 $1/2 {{2k} \choose {k}} = {{2k-1} \choose {k-1}}.$ ) Property 2 (with properties 1 and 3) reduces the theorem from general intersecting families to shifted intersecting families. Let $\cal G$ be a shifted intersecting family of $k$ -subsets of $\{1,2,3,\dots,n\}$ , $n>2k$ . We assume that the theorem holds for smaller values of $n$ . For such a family $\cal G$ , we can apply the basic inductive trick: we consider the family ${\cal G}_0$ sets in $\cal G$ not containing ‘n’, and the family ${\cal G}_1$ of those sets containing ’n’ and the family ${\cal G}'_1 = \{S \backslash \{n\}: S \in {\cal G}_1\}$ . By induction (without using the assumption that $\cal G$ is shifted) we get: $|{\cal G}_0|$ $\le {{n-2} \choose {k-1}}$ . If we could show that ${\cal G}'_1$ is an intersecting family it would follow by the induction hypothesis that $|{\cal G}_1|$ = $|{\cal G}'_1|$ $\le {{n-2} \choose {k-2}}$ and then $|{\cal G}|$ = $|{\cal G}_0|$ + $|{\cal G}_1| \le$ ${{n-2} \choose {k-1}}+$ ${{n-2} \choose {k-2}}$ $= {{n-1} \choose {k-1}}$ .

Why is ${\cal G}'_1$ an intersecting family? This is the crux of the matter. Otherwise you would have two sets $S,T$ in $\cal G$ which share only the element ‘n’. Aha, but the union of these two sets must miss one of the elements $\ell$ from $1,2, ..., n-1$ . But then we can obtain a set $R$ by deleting from $T$ the element ’n’ and adding the element ‘ $\ell$ ‘. The new set $R$ must also be in $\cal G$ ! (Here we use the fact that $\cal G$ is a shifted family.) But $R$ is disjoint to $S$ 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!

Erdös-Ko-Rado theorems

a lecture by Chris Godsil

About these ads

	Margene on Some Philosophy of Scienc…
	Seth on Navier-Stokes Fluid Computers
	John Sidles on BosonSampling and (BKS) Noise…
	ashish soni on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Joseph Malkevitch on Navier-Stokes Fluid Computers
	gowers on Polymath5 – Is 2 logarit…
	John Sidles on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	John Sidles on Navier-Stokes Fluid Computers