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!
Erdös-Ko-Rado theorems
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
Pingback: Updates and plans III. | Combinatorics and more
Pingback: Polymath10, Post 2: Homological Approach | Combinatorics and more
Hi Gil. In the “Properties of the uniform shifting”, what is the definition of the symbol delta?
Do you mean the symbol
?
Yes. The “partial derivative” symbol.
Ahh It was defined in part III. https://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/ I will add the definition to this part too.
Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more
Pingback: Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachaterian theorem, and More. | Combinatorics and more
Pingback: Beyond the g-conjecture – algebraic combinatorics of cellular spaces I | Combinatorics and more
Pingback: (Eran Nevo) The g-Conjecture III: Algebraic Shifting | Combinatorics and more
Pingback: Extremal Combinatorics V: POSETS | Combinatorics and more