6Projections
III Combinatorics
6 Projections
So far, we have been considering discrete objects only. For a change, let’s work
with something continuous.
Let K ⊆ R
n
be a bounded open set. For A ⊆ [n], we set
K
A
= {(x
i
)
i∈A
: ∃y ∈ K, y
i
− x
i
for all i ∈ A} ⊆ R
A
.
We write
|K
A
|
for the Lebesgue measure of
K
A
as a subset of
R
A
. The question
we are interested in is given some of these
|K
A
|
, can we bound
|K|
? In some
cases, it is completely trivial.
Example. If we have a partition of A
1
∪ ··· ∪ A
m
= [n], then we have
|K| ≤
m
Y
i=1
|K
A
i
|.
But, for example, in R
3
, can we bound |K| given |K
12
|, |K
13
| and |K
23
|?
It is clearly not possible if we only know, say
|K
12
|
and
|K
13
|
. For example,
we can consider the boxes
0,
1
n
× (0, n) × (0, n).
Proposition. Let K be a body in R
3
. Then
|K|
2
≤ |K
12
||K
13
||K
23
|.
This is actually quite hard to prove! However, given what we have done so
far, it is natural to try to compress
K
in some sense. Indeed, we know equality
holds for a box, and if we can make
K
look more like a box, then maybe we can
end up with a proof.
For K ⊆ R
n
, its n-sections are the sets K(x) ⊆ R
n−1
defined by
K(x) = {(x
1
, . . . , x
n−1
) ∈ R
n−1
: (x
1
, . . . , x
n−1
, x) ∈ K}.
Proof. Suppose first that each section of K is a square, i.e.
K(x) = (0, f (x)) × (0, f(x)) dx
for all x and some f. Then
|K| =
Z
f(x)
2
dx.
Moreover,
|K
12
| =
sup
x
f(x)
2
≡ M
2
, |K
13
| = |K
23
| =
Z
f(x) dx.
So we have to show that
Z
f(x)
2
dx
2
≤ M
2
Z
f(x) dx
2
,
but this is trivial, because f (x) ≤ M for all x.
Let’s now consider what happens when we compress
K
. For the general case,
define a new body L ⊆ R
3
by setting its sections to be
L(x) = (0,
p
|K(x)|) × (0,
p
|K(x)|).
Then |L| = |K|, and observe that
|L
12
| ≤ sup |K(x)| ≤
[
K(x)
= |K
12
|.
To understand the other two projections, we introduce
g(x) = |K(x)
1
|, h(x) = |K(x)
2
|.
Now observe that
|L(x)| = |K(x)| ≤ g(x)h(x),
Since
L
(
x
) is a square, it follows that
L
(
x
) has side length
≤ g
(
x
)
1/2
h
(
x
)
1/2
. So
|L
13
| = |L
23
| ≤
Z
g(x)
1/2
h(x)
1/2
dx.
So we want to show that
Z
g
1/2
h
1/2
dx
2
≤
Z
g dx
Z
h dx
.
Observe that this is just the Cauchy–Schwarz inequality applied to
g
1/2
and
h
1/2
. So we are done.
Let’s try to generalize this.
Definition ((Uniform) cover). We say a family A
1
, . . . , A
r
⊆ [n] covers [n] if
r
[
i=1
A
r
= [n],
and is a uniform k-cover if each i ∈ [n] is in exactly k many of the sets.
Example.
With
n
= 3, the singletons
{
1
}, {
2
}, {
3
}
form a 1-uniform cover,
and so does
{
1
}, {
2
,
3
}
. Also,
{
1
,
2
}, {
1
,
3
}
and
{
2
,
3
}
form a uniform 2-cover.
However, {1, 2} and {2, 3} do not form a uniform cover of [3].
Note that we allow repetitions.
Example. {1}, {1}, {2, 3}, {2}, {3} is a 2-uniform cover of [3].
Theorem
(Uniform cover inequality)
.
If
A
1
, . . . , A
r
is a uniform
k
-cover of [
n
],
then
|K|
k
=
r
Y
i=1
|K
A
|.
Proof. Let A be a k-uniform cover of [k]. Note that A is a multiset. Write
A
−
= {A ∈ A : n 6∈ A}
A
+
= {A \ {n} ∈ A : n ∈ A}
We have |A
+
| = k, and A
+
∪ A
−
forms a k-uniform cover of [n −1].
Now note that if K = R
n
and n 6∈ A, then
|K
A
| ≥ |K(x)
A
| (1)
for all x. Also, if n ∈ A, then
|K
A
| =
Z
|K(x)
A\{n}
| dx. (2)
In the previous proof, we used Cauchy–Schwarz. What we need here is H¨older’s
inequality
Z
fg dx ≤
Z
f
p
dx
1/p
Z
g
q
dx
1/q
,
where
1
p
+
1
q
= 1. Iterating this, we get
Z
f
1
···f
k
dx ≤
k
Y
i=1
Z
f
k
i
dx
1/k
.
Now to perform the proof, we induct on
n
. We are done if
n
= 1. Otherwise,
given K ⊆ R
n
and n ≥ 2, by induction,
|K| =
Z
|K(x)| dx
≤
Z
Y
A∈A
−
|K(x)
A
|
1/k
Y
A∈A
+
|K(x)
A
|
1/k
dx (by induction)
≤
Y
A∈A
−
|K
A
|
1/k
Z
Y
A∈A
+
|K(x)
A
|
1/k
dx (by (1))
≤
Y
A≤|A
−
|K
A
|
1/k
Y
A∈A
+
Z
|K(x)
A
|
1/k
(by H¨older)
=
Y
A∈A
|K
A
|
1/k
Y
A∈A
+
|K
A∪{n}
|
1/k
. (by (2))
This theorem is great, but we can do better. In fact,
Theorem
(Box Theorem (Bollob´as, Thomason))
.
Given a body
K ⊆ R
n
, i.e.
a non-empty bounded open set, there exists a box
L
such that
|L|
=
|K|
and
|L
A
| ≤ |K
A
| for all A ⊆ [n].
Of course, this trivially implies the uniform cover theorem. Perhaps more
surprisingly, we can deduce this from the uniform cover inequality.
To prove this, we first need a lemma.
Definition
(Irreducible cover)
.
A uniform
k
-cover is reducible if it is the disjoint
union of two uniform covers. Otherwise, it is irreducible.
Lemma. There are only finitely many irreducible covers of [n].
Proof.
Let
A
and
B
be covers. We say
A < B
if
A
is a “subset” of
B
, i.e. for
each A ⊆ [n], the multiplicity of A in A is less than the multiplicity in B.
Then note that the set of irreducible uniform
k
-covers form an anti-chain,
and observe that there cannot be an infinite anti-chain.
Proof of box theorem. For A an irreducible cover, we have
|K|
k
≤
Y
A∈A
|K
A
|.
Also,
|K
A
| ≤
Y
i∈A
|K
{i}
|.
Let
{x
A
:
A ⊆
[
n
]
}
be a minimal array with
x
A
≤ |K
A
|
such that for each
irreducible k-cover A, we have
|K|
k
≤
Y
A∈A
x
A
(1)
and moreover
x
A
≤
Y
i∈A
x
{i}
(2)
for all
A ⊆
[
n
]. We know this exists since there are only finitely many inequalities
to be satisfied, and we can just decrease the
x
A
’s one by one. Now again by
finiteness, for each
x
A
, there must be at least one inequality involving
x
A
on the
right-hand side that is in fact an equality.
Claim.
For each
i ∈
[
n
], there exists a uniform
k
i
-cover
C
i
containing
{i}
with
equality
|K|
k
i
=
Y
A∈C
i
x
A
.
Indeed if
x
i
occurs on the right of (1), then we are done. Otherwise, it occurs
on the right of (2), and then there is some
A
such that (2) holds with equality.
Now there is some cover
A
containing
A
such that (1) holds with equality. Then
replace A in A with {{j} : j ∈ A}, and we are done.
Now let
C =
n
[
i=1
C
i
, C
0
= C \ {{1}, {2}, . . . , {n}}, k =
n
X
i=1
k
i
.
Then
|K|
k
=
Y
A∈C
x
A
=
Y
A∈C
1
x
A
!
≥ |K|
k−1
n
Y
i=1
x
i
.
So we have
|K| ≥
n
Y
i=1
x
i
.
But we of course also have the reverse inequality. So it must be the case that
they are equal.
Finally, for each
A
, consider
A
=
{A} ∪ {{i}
:
i 6∈ A}
. Then dividing (1) by
Q
i∈A
x
i
gives us
Y
i6∈A
x
i
≤ x
A
.
By (2), we have the inverse equality. So we have
x
A
=
Y
i∈A
x
i
for all i. So we are done by taking L to be the box with side length x
i
.
Corollary.
If
K
is a union of translates of the unit cube, then for any (not
necessarily uniform) k-cover A, we have
|K|
k
≤
Y
A∈A
|K
A
|.
Here a k-cover is a cover where every element is covered at least k times.
Proof.
Observe that if
B ⊆ A
, then
|K
B
| ≤ |K
A
|
. So we can reduce
A
to a
uniform k-cover.