Extremal Combinatorics IV: Shifting

Posted on October 6, 2008 by

 

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

Advertisements
This entry was posted in Combinatorics, Open problems and tagged , . Bookmark the permalink.

13 Responses to Extremal Combinatorics IV: Shifting

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

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

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

  4. Pingback: Leslie Valiant and the PAC Model « Tsourolampis Blog

  5. Pingback: Updates and plans III. | Combinatorics and more

  6. Pingback: Polymath10, Post 2: Homological Approach | Combinatorics and more

  7. ssbmplayer says:
    March 22, 2017 at 7:08 pm

    Hi Gil. In the “Properties of the uniform shifting”, what is the definition of the symbol delta?

    Reply

  8. Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more

  9. Pingback: Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachaterian theorem, and More. | Combinatorics and more

  10. Pingback: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I | Combinatorics and more

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )

w
Cancel

Connecting to %s