3The Kruskal–Katona theorem
III Combinatorics
3 The Kruskal–Katona theorem
For A ⊆ X
(r)
, recall we defined the lower shadow to be
∂A = {B ∈ X
(r−1)
: B ⊆ A for some A ∈ A}.
The question we wish to understand is how small we can make
∂A
, relative to
A. Crudely, we can bound the size by
|∂A| ≥ |A|
n
r−1
n
r
=
n − r
r
|A|.
But surely we can do better than this. To do so, one reasonable strategy is to
first produce some choice of
A
we think is optimal, and see how we can prove
that it is indeed optimal.
To do so, let’s look at some examples.
Example. Take n = 6 and r = 3. We pick
A = {123, 456, 124, 256}.
Then we have
∂A = {12, 13, 23, 45, 46, 56, 14, 24, 25, 26},
and this has 10 elements.
But if we instead had
A = {123, 124, 134, 234},
then
∂A = {12, 13, 14, 23, 24, 34},
and this only has 6 elements, and this is much better.
Intuitively, the second choice of
A
is better because the terms are “bunched”
together.
More generally, we would expect that if we have
|A|
=
k
r
, then the best
choice should be
A
= [
k
]
(r)
, with
|∂A|
=
k
r−1
. For other choices of
A
, perhaps
a reasonable strategy is to find the largest
k
such that
k
r
< |A|
, and then take
A
to be [
k
]
(r)
plus some elements. To give a concrete description of which extra
elements to pick, our strategy is to define a total order on [
n
]
(r)
, and say we
should pick the initial segment of length |A|.
This suggests the following proof strategy:
(i)
Come up with a total order on [
n
]
(r)
, or even
N
(r)
such that [
k
]
(r)
are
initial segments for all k.
(ii)
Construct some “compression” operators
P
(
N
(r)
)
→ P
(
N
(r)
) that pushes
each element down the ordering without increasing the |∂A|.
(iii)
Show that the only subsets of
N
(r)
that are fixed by the compression
operators are the initial segments.
There are two natural orders one can put on [n]
(r)
:
– lex: We say A < B if min A∆B ∈ A.
– colex: We say A < B if max A∆B ∈ B.
Example. For r = 3, the elements of X
(3)
in colex order are
123, 124, 134, 234, 125, 135, 235, 145, 245, 345, 126, . . .
In fact, colex is an order on
N
(r)
, and we see that the initial segment with
n
r
elements is exactly [n]
(r)
. So this is a good start.
If we believe that colex is indeed the right order to do, then we ought to
construct some compression operators. For
i 6
=
j
, we define the (
i, j
)-compression
as follows: for a set A ∈ X
(r)
, we define
C
ij
(A) =
(
(A \ {j}) ∪ {i} j ∈ A, i 6∈ A
A otherwise
For a set system, we define
C
ij
(A) = {C
ij
(A) : A ∈ A} ∪ {A ∈ A : C
ij
(A) ∈ A}
We can picture our universe of sets as follows:
B ∪ {j}
B ∪ {i}
The set system
A
is some subset of all these points, and we what we are doing
is that we are pushing everything down when possible.
It is clear that we have |C
ij
(A)| = |A|. We further observe that
Lemma. We have
∂C
ij
(A) ⊆ C
ij
(∂A).
In particular, |∂C
ij
(A)| ≤ |∂A|.
Given
A ⊆ X
(r)
, we say
A
is left-compressed if
c
ij
(
A
) =
A
for all
i < j
. Is
this good enough?
Of course initial segments are left-compressed. However, it turns out the
converse is not true.
Example. {123, 124, 125, 126} are left-compressed, but not an initial segment.
So we want to come up with “more powerful” compressions. For
U, V ∈ X
(s)
with
U ∩V
=
∅
, we define a (
U, V
)-compression as follows: for
A ⊆ X
, we define
C
UV
(A) =
(
(A \ V ) ∪ U A ∩ (U ∪ V ) = V
A otherwise
Again, for A ⊆ X
(r)
, we can define
C
UV
(A) = {C
UV
(A) : A ∈ A} ∪ {A ∈ A : C
UV
(A) ∈ A}.
Again, A is (U, V )-compressed if C
UV
(A) = A.
This time the behaviour of the compression is more delicate.
Lemma.
Let
A ⊆ X
(r)
and
U, V ∈ X
(s)
,
U ∩ V
=
∅
. Suppose for all
u ∈ U
,
there exists v such that A is (U \ {u}, V \ {v})-compressed. Then
∂C
UV
(A) ⊆ C
UV
(∂A).
Lemma. A ⊆ X
(r)
is an initial segment of
X
(r)
in colex if and only if it is
(U, V )-compressed for all U, V disjoint with |U| = |V | and max V > max U.
Proof. ⇒
is clear. Suppose
A
is (
U, V
) compressed for all such
U, V
. If
A
is not
an initial segment, then there exists
B ∈ A
and
C 6∈ A
such that
C < B
. Then
A is not (C \ B, B \ C)-compressed. A contradiction.
Lemma.
Given
A ∈ X
(r)
, there exists
B ⊆ X
(r)
such that
B
is (
U, V
)-
compressed for all |U| = |V |, U ∩ V = ∅, max V > max U, and moreover
|B| = |A|, |∂B| ≤ |∂A|. (∗)
Proof. Let B be such that
X
B∈B
X
i∈B
2
i
is minimal among those
B
’s that satisfy (
∗
). We claim that this
B
will do. Indeed,
if there exists (
U, V
) such that
|U|
=
|V |
,
max V > max U
and
C
UV
(
B
)
6
=
B
,
then pick such a pair with
|U|
minimal. Then apply a (
U, V
)-compression, which
is valid since given any
u ∈ U
we can pick any
v ∈ V
that is not
max V
to satisfy
the requirements of the previous lemma. This decreases the sum, which is a
contradiction.
From these, we conclude that
Theorem
(Kruskal 1963, Katona 1968)
.
Let
A ⊆ X
(r)
, and let
C ⊆ X
(r)
be
the initial segment with |C| = |A|. Then
|∂A| ≥ |∂C|.
We can now define the shadow function
∂
(r)
(m) = min{|∂A| : A ⊆ X
(r)
, |A| = m}.
This does not depend on the size of
X
as long as
X
is large enough to accommo-
date
m
sets, i.e.
n
r
≥ m
. It would be nice if we can concretely understand this
function. So let’s try to produce some initial segments.
Essentially by definition, an initial segment is uniquely determined by the
last element. So let’s look at some examples.
Example.
Take
r
= 4. What is the size of the initial segment ending in 3479?
We note that anything that ends in something less than 8 is less that 3479,
and there are
8
4
such elements. If you end in 9, then you are still fine if the
second-to-last digit is less than 7, and there are
6
3
such elements. Continuing,
we find that there are
8
4
+
6
3
+
4
2
such elements.
Given
m
r
> m
r−1
> ··· > m
s
≥ s
, we let
B
(r)
(
m
r
, m
r−1
, . . . , m
s
) be the
initial segment ending in the element
m
r
+ 1, m
r−1
+ 1, . . . , m
s+1
+ 1, m
s
, m
s
− 1, m
s
− 2, . . . , m
s
− (s − 1).
This consists of the sets
{a
1
< a
2
< ··· < a
r
}
such that there exists
j ∈
[
s, r
]
with a
i
= m
i
+ 1 for i > j, and a
j
≤ m
j
.
To construct an element in
B
(r)
(
m
r
, . . . , m
s
), we need to first pick a
j
, and
then select j elements that are ≤ m
j
. Thus, we find that
|B
(r)
(m
r
, . . . , m
s
)| =
r
X
j=s
m
j
j
= b
(r)
(m
1
, . . . , m
s
).
We see that this
B
(r)
is indeed the initial segment in the colex order ending
in that element. So we know that for all
m ∈ N
, there is a unique sequence
m
r
> m
r−1
> . . . , > m
s
≥ s such that n =
P
r
j=0
m
j
j
.
It is also not difficult to find the shadow of this set. After a bit of thinking,
we see that it is given by
B
(r−1)
(m
r
, . . . , m
s
).
Thus, we find that
∂
(r)
r
X
i=s
m
i
i
!
=
r
X
i=s
m
i
i − 1
,
and moreover every
m
can be expressed in the form
P
r
i=s
m
i
i
for some unique
choices of m
i
.
In particular, we have
∂
(r)
n
r
=
n
r − 1
.
Since it might be slightly annoying to write
m
in the form
P
r
i=s
m
i
i
, Lov´asz
provided another slightly more convenient bound.
Theorem (Lov´asz, 1979). If A ⊆ X
(r)
with |A| =
x
r
for x ≥ 1, x ∈ R, then
|∂A| ≥
x
r − 1
.
This is best possible if x is an integer.
Proof. Let
A
0
= {A ∈ A : 1 6∈ A}
A
1
= {A ∈ A : 1 ∈ A}.
For convenience, we write
A
1
− 1 = {A \ {1} : A ∈ A
1
}.
We may assume
A
is (
i, j
)-compressed for all
i < j
. We induct on
r
and then on
|A|. We have
|A
0
| = |A| − |A
1
|.
We note that A
1
is non-empty, as A is left-compressed. So |A
0
| < |A|.
If r = 1 and |A| = 1 then there is nothing to do.
Now observe that
∂A ⊆ A
1
−
1, since if
A ∈ A
, 1
6∈ A
, and
B ⊆ A
is such
that
|A \ B|
= 1, then
B ∪ {
1
} ∈ A
1
since
A
is left-compressed. So it follows
that
|∂A
0
| ≤ |A
1
|.
Suppose |A
1
| <
x−1
r−1
. Then
|A
0
| >
x
r
−
x − 1
r − 1
=
x − 1
r
.
Therefore by induction, we have
|∂A
0
| >
x − 1
r − 1
.
This is a contradiction, since
|∂A
0
| ≤ |A
1
|
. Hence
|A
1
| ≥
x−1
r−1
. Hence we are
done, since
|∂A| ≥ |∂A
1
| = |A
1
| + |∂(A
1
− 1)| ≥
x − 1
r − 1
+
x − 1
r − 2
=
x
r − 1
.