4Isoperimetric inequalities

III Combinatorics


4 Isoperimetric inequalities
We are now going to ask a question similar to the one answered by Kruskal–
Katona. Kruskal–Katona answered the question of how small can
∂A
be among
all
A ⊆ X
(r)
of fixed size. Clearly, we obtain the same answer if we sought to
minimized the upper shadow instead of the lower. But what happens if we want
to minimize both the upper shadow and the lower shadow? Or, more generally,
if we allow
A ⊆ P
(
X
) to contain sets of different sizes, how small can the set of
“neighbours” of A be?
Definition
(Boundary)
.
Let
G
be a graph and
A ⊆ V
(
A
). Then the boundary
b(A) is the set of all x ∈ G such that x 6∈ A but x is adjacent to A.
Example. In the following graph
the boundary of the green vertices is the red vertices.
An isoperimetric inequality on G is an inequality of the form
|b(A)| ≥ f(|A|)
for all
A ⊆ G
. Of course, we could set
f ≡
0, but we would like to do better
than that.
The “continuous version” of this problem is well-known. For example, in a
plane, given a fixed area, the perimeter of the area is minimized if we pick the
area to be a disc. Similarly, among subsets of
R
3
of a given volume, the solid
sphere has the smallest surface area. Slightly more exotically, among subsets of
S
2
of given area, the circular cap has smallest perimeter.
Before we proceed, we note the definition of a neighbourhood:
Definition
(Neighbourhood)
.
Let
G
be a graph and
A ⊆ V
(
A
). Then the
neighbourhood of A is N (A) = A ∪ b(A).
Of course,
|b
(
A
)
|
=
|N
(
A
)
| − |A|
, and it is often convenient to express and
prove our isoperimetric inequalities in terms of the neighbourhood instead.
If we look at our continuous cases, then we observe that all our optimal
figures are balls, i.e. they consist of all the points a distance at most
r
from a
point, for some
r
and single point. We would hope that this pattern generalizes.
Of course, it would be a bit ambitious to hope that balls are optimal for all
graphs. However, we can at least show that it is true for the graphs we care
about, namely graphs obtained from power sets.
Definition
(Discrete cube)
.
Given a set
X
, we turn
P
(
X
) into a graph as
follows: join
x
to
y
if
|x
∆
y|
= 1, i.e. if
x
=
y ∪{a}
for some
a 6∈ y
, or vice versa.
This is the discrete cube Q
n
, where n = |X|.
Example. Q
3
looks like
123
1312 23
21 3
∅
This looks like a cube! Indeed, if we identify each
x ∈ Q
with the 0-1 sequence
of length
n
(e.g. 13
7→
101000
···
0), or, in other words, its indicator function,
then Q
n
is naturally identified with the unit cube in R
n
.
∅
1
3
2 12
13
23 123
Note that in this picture, the topmost layer is the points that do have 3, and the
bottom layer consists of those that do not have a 3, and we can make similar
statements for the other directions.
Example.
Take
Q
3
, and try to find a size
A
of size 4 that has minimum
boundary. There are two things we might try — we can take a slice, or we can
take a ball. In this case, we see the ball is the best.
We can do more examples, and it appears that the ball
X
(≤r)
is the best all
the time. So that might be a reasonable thing to try to prove. But what if we
have |A| such that |X
(≤r)
| < |A| < |X
(≤r+1)
?
It is natural to think that we should pick an
A
with
X
(≤r)
⊆ A ⊆ X
(≤r+1)
,
so we set
A
=
X
(≤r)
∪B
, where
B ⊆ X
(r+1)
. Such an
A
is known as a Hamming
ball.
What B should we pick? Observe that
N(A) = X
(≤r+1)
∪ ∂
+
B.
So we want to pick
B
to minimize the upper shadow. So by Kruskal–Katona,
we know we should pick B to be the initial segment in the lex order.
Thus, if we are told to pick 1000 points to minimize the boundary, we go up
in levels, and in each level, we go up in lex.
Definition
(Simplicial ordering)
.
The simplicial ordering on
Q
n
is defined by
x < y if either |x| < |y|, or |x| = |y| and x < y in lex.
Our aim is to show that the initial segments of the simplicial order minimize
the neighbourhood. Similar to Kruskal–Katona, a reasonable strategy would be
to prove it by compression.
For
A ⊆ Q
n
, and 1
≤ i ≤ n
, the
i
-sections of
A
are
A
(i)
+
, A
(i)
−
⊆ P
(
X \ {i}
)
defined by
A
(i)
−
= {x ∈ A : i 6∈ x}
A
(i)
+
= {x \ {i} : x ∈ A, i ∈ x}.
These are the top and bottom layers in the i direction.
The
i
-compression (or co-dimension 1 compression) of
A
is
C
i
(
A
), defined by
C
i
(A)
+
= first |A
+
| elements of P(X \ {i}) in simplicial
C
i
(A)
−
= first |A
−
| elements of P(X \ {i}) in simplicial
Example. Suppose we work in Q
4
, where the original set is
i
The resulting set is then
i
Clearly, we have
|C
i
(
A
)
|
=
|A|
, and
C
i
(
A
) “looks more like” an initial segment
in simplicial ordering than A did.
We say A is i-compressed if C
i
(A) = A.
Lemma. For A ⊆ Q
n
, we have |N (C
i
(A))| ≤ |N(A)|.
Proof. We have
|N(A)| = |N(A
+
) ∪ A
−
| + |N(A
−
) ∪ A
+
|
Take B = C
i
(A). Then
|N(B)| = |N(B
+
) ∪ B
−
| + |N(B
−
) ∪ B
+
|
= max{|N(B
+
)|, |B
−
|} + max{|N(B
−
)|, |B
+
|}
≤ max{|N(A
+
)|, |A
−
|} + max{|N(A
−
)|, |A
+
|}
≤ |N(A
+
) ∪ A
i
| + |N(A
−
) ∪ A
+
|
= |N(A)|
Since each compression moves us down in the simplicial order, we can keep
applying compressions, and show that
Lemma. For any A ⊆ Q
n
, there is a compressed set B ⊆ Q
n
such that
|B| = |A|, |N(B)| ≤ |N(A)|.
Are we done? Does being compressed imply being an initial segment? No!
For
n
= 3, we can take
{∅,
1
,
2
,
12
}
, which is obviously compressed, but is not
an initial segment. To obtain the actual initial segment, we should replace 12
with 3.
∅
1
3
2 12
13
23 123
For
n
= 4, we can take
{∅,
1
,
2
,
3
,
4
,
12
,
13
,
23
}
, which is again compressed by
not an initial segment. It is an initial segment only if we replace 23 with 14.
∅
1
3
2 12
13
23 123
4 14
34
24 124
134
234 1234
We notice that these two examples have a common pattern. The “swap” we
have to perform to get to an initial segment is given by replacing an element
with its complement, or equivalently, swapping something the opposite diagonal
element. This is indeed general.
Lemma.
For each
n
, there exists a unique element
z ∈ Q
n
such that
z
c
is the
successor of z.
Moreover, if
B ⊆ Q
n
is compressed but not an initial segment, then
|B|
=
2
n−1
and
B
is obtained from taking the initial segment of size 2
n−1
and replacing
x with x
c
.
Proof.
For the first part, simply note that complementation is an order-reversing
bijection
Q
n
→ Q
n
, and
|Q
n
|
is even. So the 2
n−1
th element is the only such
element z.
Now if
B
is not an initial segment, then we can find some
x < y
such that
x 6∈ B
and
y ∈ B
. Since
B
is compressed, it must be the case that for each
i
,
there is exactly one of
x
and
y
that contains
i
. Hence
x
=
y
c
. Note that this is
true for all
x < y
such that
x 6∈ B
and
y ∈ B
. So if we write out the simplicial
order, then B must look like
···
since any
x 6∈ B
such that
x < y
must be given by
x
=
y
c
, and so there must be
a unique such
x
, and similarly the other way round. So it must be the case that
y is the successor of x, and so x = z.
We observe that these anomalous compressed sets are worse off than the
initial segments (exercise!). So we deduce that
Theorem
(Harper, 1967)
.
Let
A ⊆ Q
n
, and let
C
be the initial segment in the
simplicial order with |C| = |A|. Then |N(A)| ≥ |N (C)|. In particular,
|A| =
r
X
i=0
n
i
implies |N(A)| ≥
r+1
X
i=0
n
i
.
The edge isoperimetric inequality in the cube
Let
A ⊆ V
be a subset of vertices in a graph
G
= (
V, E
). Consider the edge
boundary
∂
e
A = {xy ∈ E : x ∈ A, y 6∈ A}.
Given a graph
G
, and given the size of
A
, can we give a lower bound for the size
of ∂
e
A?
Example.
Take
G
=
Q
3
. For the vertex isoperimetric inequality, our optimal
solution with |A| = 4 was given by
∅
1
3
2 12
13
23 123
The edge boundary has size 6. However, if we just pick a slice, then the edge
boundary has size 4 only.
More generally, consider
Q
n
=
Q
2k+1
, and take the Hamming ball
B
k
=
X
(≤`)
. Then
∂
e
B
k
= {AB : A ⊆ B ⊆ X : |A| = k, |B| = k + 1}.
So we have
|∂
e
B
k
| =
2k + 1
k + 1
· (k + 1) ∼
2
n
√
n
√
2π
.
However, if we pick the bottom face of
Q
n
. Then
|A|
= 2
n−1
and
|∂
e
A|
= 2
n−1
.
This is much much better.
More generally, it is not unreasonable to suppose that sub-cubes are always
the best. For a k-dimensional sub-cube in Q
n
, we have
|∂
k
| = 2
k
(n − k).
If we want to prove this, and also further solve the problem for
|A|
not a power
of 2, then as our previous experience would suggest, we should define an order
on P(X).
Definition
(Binary order)
.
The binary order on
Q
n
∼
=
P
(
X
) is given by
x < y
if max x∆y ∈ y.
Equivalently, define ϕ : P(X) → N by
ϕ(x) =
X
i∈x
2
i
.
Then x < y if ϕ(x) < ϕ(y).
The idea is that we avoid large elements. The first few elements in the
elements would like like
∅, 1, 2, 123, 13, 23, 123, . . . .
Theorem.
Let
A ⊆ Q
n
be a subset, and let
C ⊆ Q
n
be the initial segment of
length |A| in the binary order. Then |∂
e
C| ≤ |∂
e
A|.
Proof.
We induct on
n
using codimension-1 compressions. Recall that we
previously defined the sets A
(i)
±
.
The
i
-compression of
A
is the set
B ⊆ Q
n
such that
|B
(i)
±
|
=
|A
(i)
±
|
, and
B
(i)
±
are initial segments in the binary order. We set D
i
(A) = B.
Observe that performing
D
i
reduces the edge boundary. Indeed, given any
A, we have
|∂
e
A| = |∂
e
A
(i)
+
| + |∂
e
A
(i)
−
| + |A
(i)
+
∆A
(i)
i
|.
Applying
D
i
clearly does not increase any of those factors. So we are happy.
Now note that if A 6= D
i
A, then
X
x∈A
X
i∈x
2
i
<
X
x∈D
i
A
X
i∈x
2
i
.
So after applying compressions finitely many times, we are left with a compressed
set.
We now hope that a compressed subset must be an initial segment, but this
is not quite true.
Claim. If A is compressed but not an initial, then
A =
˜
B = P(X \ {n}) \ {123 ···(n − 1)} ∪ {n}.
By direct computation, we have
|∂
e
˜
B| = 2
n−1
− 2(n − 2),
and so the initial segment is better. So we are done.
The proof of the claim is the same as last time. Indeed, by definition, we can
find some
x < y
such that
x 6∈ A
and
y ∈ A
. As before, for any
i
, it cannot be
the case that both
x
and
y
contain
i
or neither contain
i
, since
A
is compressed.
So x = y
c
, and we are done as before.