Isoperimetric Inequalities - Combinatorics

2 Isoperimetric Inequalities

“How do we minimise the boundary of a set of given size?”

Example. Among all subsets of $ℝ^{2}$ of given area, the disc minimises the perimeter.

Among all subsets of $ℝ^{3}$ of given volume, the solid sphere minimises the surface area.

Among all subsets of $S^{2}$ of given surface area, the circular arc has the smallest perimeter.

Definition (Boundary in a graph). For a set $A$ of vertices of a graph $G$ , the boundary of $A$ is

b (A) = {x \in G : x \notin A, x y \in E for some y \in A} .

Example. Here, if $A = {1, 2, 4}$ , then $b (A) = {3, 5}$ .

Definition (Isoperimetric inequality). An isoperimetric inequality on $G$ is an inequality of the form

| b (A) | \geq f (| A |) \forall A \subset G,

for some function $f$ .

Definition (Neighbourhood). Often simpler to look at the neighbourhood of $A$ : $N (A) = A \cup b (A)$ . So

N (A) = {x \in G : d (x, A) \leq 1} .

A good example for $A$ might be a ball $B (x, r) = {y \in G : d (x, y) \leq r}$ . What happens for $Q_{n}$ ?

Example. $| A | = 4$ in $Q_{3}$ .

Good guess that balls are best, i.e. sets of the form $B (\emptyset, r) = X^{(\leq r)} = X^{(0)} \cup X^{(1)} \cup \dots \cup X^{(r)}$ .

What if $| X^{(\leq r)} | < | A | < | X^{(r + 1)} |$ ?

Guess: take $A$ with $X^{(\leq r)} < A < X^{(\leq r + 1)}$ . If $A = X^{(\leq r)} \cup B$ , where $B \subset X^{(r + 1)}$ , then $b (A) = (X^{(r + 1)} - B) \cup \partial^{+} B$ . So we’d take $B$ to be an initial segment of lexicographic (by Kruskal-Katona).

This suggests...

In the simplicial ordering on $P (X)$ , we set $x < y$ if either $| x | < | y |$ or $| x | = | y |$ and $x < y$ in lexicographic.

Aim: initial segments of simplicial ordering minimise the boundary.

Definition ( $i$ -sections). For $A \subset P (X)$ and $1 \leq i \leq n$ , the $i$ -sections of $A$ are the families $A_{-}^{(i)}, A_{+}^{(i)} \subset P (X - i)$ given by:

\begin{array}{l} A_{-}^{(i)} & = {x \in A : i \notin x} \\ A_{+}^{(i)} & = {x - i : x \in A, i \in x} \end{array}

The $i$ -compression of $A$ in the family $C_{i} (A) \subset P (X)$ given by:

${(C_{i} (A))}_{-}^{(i)}$ is the first $| A_{-}^{(i)} |$ elements of simplicial ordering on $P (X - i)$
${(C_{i} (A))}_{+}^{(i)}$ is the first $| A_{+}^{(i)} |$ elements of simplicial ordering on $P (X - i)$

Example.

Certainly $| C_{i} (A) | = | A |$ . Say $A$ is $i$ -compressed if $C_{i} (A) = A$ . Also, $C_{i} (A)$ “looks more like” a Hamming ball than $A$ does.

Here, a Hamming ball is a family $A$ with $X^{(\leq r)} \subset A \subset X^{(\leq r + 1)}$ , for some $r$ .

Theorem 1 (Harper’s Theorem). Assuming that:

$A \subset Q_{n}$
$C$ the initial segment of simplicial ordering with $| C | = | A |$

Then

| N (A) | \geq | N (C) |

. In particular, if

| A | = \sum_{i = 0}^{r} (\binom{n}{i})

then

| N (A) | \geq \sum_{i = 0}^{r + 1} (\binom{n}{i})

Remark.

(1) If we knew $A$ was a Hamming ball, then we would be done by Kruskal-Katona.
(2) Conversely, Harper’s Theorem implies Kruskal-Katona: given $B \subset X^{(r)}$ , then apply Harper’s Theorem to $A = X^{(\leq r - 1)} \cup B$ .

Proof. Induction on $n$ : $n = 1$ is trivial.

Given $n > 1$ , and $A \subset Q_{n}$ , and $1 \leq i \leq n$ .

Claim: $| N (C_{i} (A)) | \leq | N (A) |$ .

Proof of claim: Write $B$ for $C_{i} (A)$ . We have

\begin{array}{l} N {(A)}_{-} & = N (A_{-}) \cup A_{+} \\ N {(A)}_{+} & = N (A_{+}) \cup A_{-} \end{array}

and of course

\begin{array}{l} N {(B)}_{-} & = N (B_{-}) \cup B_{+} \\ N {(B)}_{+} & = N (B_{+}) \cup B_{-} \end{array}

Now, $| B_{+} | = | A_{+} |$ and $| N (B_{-}) | \leq | N (A_{-}) |$ (by the induction hypothesis). But $B_{+}$ is an initial segment of simplicial ordering, and $N (B_{-})$ is an initial segment of simplicial ordering (as neighbourhood of initial segment is an initial segment).

So then $B_{+}$ and $N (B_{-})$ are nested (one conatined in the other). Hence $| N {(B)}_{-} | \leq | N {(A)}_{-} |$ . Similarly, $| N {(B)}_{+} | \leq | N {(A)}_{+} |$ .

Hence $| N (B) | \leq | N (A) |$ , which completes the proof of our claim. □

Define a sequence $A_{0}, A_{1}, \dots \subset Q_{n}$ as follows:

Set $A_{0} = A_{1}$ .
Having chosen $A_{0}, \dots, A_{k}$ : if $A_{k}$ is $i$ -compressed with $C_{i} (A_{k}) \neq A_{k}$ and set $A_{k + 1} = C_{i} (A_{k})$ – and continue.

Must terminate, because $\sum_{x \in A_{k}} (position of x in simplicial ordering)$ is strictly decresing.

The final family $B = A_{k}$ satisfies $| B | = | A |$ , $| N (B) | \leq | N (A) |$ , and is $i$ -compressed for all $i$ . Does $B$ $i$ -compressed for all $i$ imply that $B$ is an initial segment of simplicial ordering? (If yes, then $B = C$ and we are done).

Sadly, no. For example in $Q_{3}$ can take ${\emptyset, 1, 2, 12}$ :

However:

Lemma 2. Assuming that:

$B \subset Q_{n}$ is $i$ -compressed for all $i$
$B$ not an initial segment of the simplicial ordering

Then one of the following is true:

either $n$ is odd, say $n = 2 k + 1$ , and $B = X^{(\leq k)} - {k + 2, k + 3, \dots, 2 k + 1} \cup {1, 2, \dots, k + 1}$
or $n$ is even, say $n = 2 k$ , and $B = X^{(< k)} \cup {x \in X^{(k)} : 1 \in x} - {1, k + 2, k + 3, \dots, 2 k} \cup {2, 3, 4, \dots, k + 1}$ .

For the even case: “Remove the last $k$ -set with $1$ , and add the first $k$ -set without $1$ .”

After we prove this, we will have solved our problem, as in each case we certainly have $| N (B) | \geq | N (C) |$ .

Proof. Since $B$ is not an initial segment of simplicial ordering, there exists $x < y$ (in simplicial ordering) with $x \notin B$ , $y \in B$ .

For each $1 \leq i \leq n$ : cannot have $i \in x$ , $i \in y$ (as $B$ is $i$ -compressed). Also cannot have $i \notin x$ , $i \notin y$ for the same reason.

So $x = y^{c}$ .

Thus: for each $y \in B$ , there exists at most one earlier $x$ with $x \notin B$ (namely $x = y^{c}$ ). Similarly, for each $x \notin B$ there is at most one later $y$ with $y \in B$ (namely $y = x^{c}$ ).

So $B = {z : z \leq y} - {x}$ , with $x$ the predessor of $y$ and $x = y^{c}$ .

Hence if $n = 2 k + 1$ then $x$ is the last $k$ -set, and if $n = 2 k$ then $x$ is the last $k$ -set with $1$ . □

Proof of Theorem 1. Done by above. □

Remark.

(1) Can also prove Harper’s Theorem $U V$ -compressions.
(2) Can also prove Kruskal-Katona using these ‘codimension $1$ ’ compressions.

For $A \subset Q_{n}$ and $t = 1, 2, 3, \dots$ , the $t$ -neighbourhood of $A$ is $A_{(t)} = N^{t} (A) = {x \in Q_{n} : d (x, A) \leq t}$ .

Corollary 3. Let $A \subset Q_{n}$ with $| A | \geq \sum_{i = 0}^{r} (\binom{n}{i})$ . Then

| A_{(t)} | \geq \sum_{i = 0}^{r + t} (\binom{n}{i})

for all $t \leq n - r$ .

Proof. Theorem 1 with induction on $t$ . □

To get a feeling for the strength of Corollary 3, we’ll need some estimates on things like $\sum_{i = 0}^{r} (\binom{n}{i})$ .

“Going $𝜀 \sqrt{n}$ standard deviations away from the mean $\frac{n}{2}$ .”

Proposition 4. Assuming that:

$0 < 𝜀 < \frac{1}{4}$

Then

\sum_{i = 0}^{⌊ (\frac{1}{2} - 𝜀) n ⌋} (\binom{n}{i}) \leq \frac{1}{𝜀} e^{- \frac{𝜀^{2} n}{2}} \cdot 2^{n} .

“For $𝜀$ fixed, $n \to \infty$ , this is an exponentially small fraction of $2^{n}$ .”

Proof. For $i \leq ⌊ (\frac{1}{2} - 𝜀) n ⌋$ :

(\binom{n}{i}) = (\binom{n}{i}) \frac{i}{n - i + 1},

\frac{(\binom{n}{i - 1})}{(\binom{n}{i})} = \frac{i}{n - i + 1} \leq \frac{(\frac{1}{2} - 𝜀) n}{(\frac{1}{2} + 𝜀) n} = \frac{\frac{1}{2} - 𝜀}{\frac{1}{2} + 𝜀} = 1 - \frac{2 𝜀}{\frac{1}{2} + 𝜀} \leq 1 - 2 𝜀 .

Hence

\sum_{i = 0}^{⌊ (\frac{1}{2} - 𝜀) n ⌋} (\binom{n}{i}) \leq \frac{1}{2 𝜀} (\binom{n}{⌊ (\frac{1}{2} - 𝜀) n ⌋})

(sum of a geometric progression).

Same argument tells us that

\begin{array}{l} (\binom{n}{⌊ (\frac{1}{2} - 𝜀) n ⌋}) & \leq (\binom{n}{⌊ (\frac{1}{2} - \frac{𝜀}{2}) n ⌋}) {(1 - 2 \frac{𝜀}{2})}^{\frac{𝜀 n}{2} - 1} & -1 from the ⌊ ∙ ⌋ stuff \\ \leq 2^{n} \cdot 2 {(1 - 𝜀)}^{\frac{𝜀 n}{2}} \\ \leq 2^{n} \cdot 2 e^{- \frac{𝜀^{2} n}{2}} & as 1 - 𝜀 \leq e^{- 𝜀} \end{array}

Thus

\sum_{i = 0}^{⌊ (\frac{1}{2} - 𝜀) n ⌋} (\binom{n}{i}) \leq \frac{1}{2 𝜀} \cdot 2 e^{- \frac{𝜀^{2} n}{2}} \cdot 2^{n} . □

Theorem 5. Assuming that:

$0 < 𝜀 < \frac{1}{4}$
$A \subset Q_{n}$
$\frac{| A |}{2^{n}} \geq \frac{1}{2}$

Then

\frac{| A_{(𝜀 n)} |}{2^{n}} \geq 1 - \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}}

“ $\frac{1}{2}$ -sized sets have exponentially large $𝜀 n$ -neighbourhoods.”

Proof. Enough to show that if $𝜀 n$ an integer then

\frac{| A_{(𝜀 n)} |}{2^{n}} \geq 1 - \frac{1}{𝜀} e^{- \frac{𝜀^{2} n}{2}} .

Have $| A | \geq \sum_{i = 0}^{⌈ \frac{n}{2} - 1 ⌉} (\binom{n}{i})$ , so by Harper’s Theorem, we have $| A_{(𝜀 n)} | \geq \sum_{i = 0}^{⌈ \frac{n}{2} - 1 + 𝜀 n ⌉} (\binom{n}{i})$ , so

| A_{(𝜀 n)}^{c} | \leq \sum_{i = ⌈ \frac{n}{2} + 𝜀 n ⌉}^{n} (\binom{n}{i}) = \sum_{i = 0}^{⌊ \frac{n}{2} - 𝜀 n ⌋} (\binom{n}{i}) \leq \frac{1}{𝜀} e^{- \frac{𝜀^{2} n}{2}} 2^{n} . □

Remark. Same would show, for “small” sets:

\frac{| A |}{2^{n}} \geq \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}} ⟹ \frac{| A_{(2 𝜀 n)} |}{2^{n}} \geq 1 - \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}} .

2.1 Concentration of measure

Say $f : Q_{n} \to ℝ$ is Lipschitz if $| f (x) - f (y) | \leq 1$ for all $x, y$ adjacent.

For $f : Q_{n} \to ℝ$ , say $M \in ℝ$ is a Lévy mean or median of $f$ if

| {x \in Q_{n} : f (x) \leq M} | \geq 2^{n - 1}

and

| {x \in Q_{n} : f (x) \geq M} | \geq 2^{n - 1}

Now ready to show “every well-behaved function on the cube $Q_{n}$ is roughly constant nearly everywhere”.

Theorem 6. Assuming that:

$f : Q_{n} \to ℝ$ Lipschitz with median $M$

Then

\frac{| {x : | f (x) - M | \leq 𝜀 n} |}{2^{n}} \geq 1 - \frac{4}{𝜀} e^{- \frac{𝜀^{2} n}{2}}

for any $0 < 𝜀 < \frac{1}{4}$ .

Note. This is the “concentration of measure” phenomenon.

Proof. Let $A = {x : f (x) \leq M}$ . Then $\frac{| A |}{2^{n}} \geq \frac{1}{2}$ , so

\frac{| A_{(𝜀 n)} |}{2^{n}} \geq 1 - \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}} .

ut $f$ is Lipschitz, so $x \in A_{(𝜀 n)}$ implies $f (x) \leq M + 𝜀 n$ . Thus

\frac{| {x : f (x) \leq M + 𝜀 n} |}{2^{n}} \geq 1 - \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}} .

Similarly,

\frac{| {x : f (x) \geq M - 𝜀 n} |}{2^{n}} \geq 1 - \frac{2}{𝜀} e^{- \frac{𝜀^{2} n}{2}} .

Hence

\frac{| {x : M - 𝜀 n \leq f (x) \leq M + 𝜀 n} |}{2^{n}} \geq 1 - \frac{4}{𝜀} e^{- \frac{𝜀^{2} n}{2}} . □

Let $G$ be a graph of diameter $D$ ( $D = \max {f (x, y) : x, y \in G}$ ).

Definition ( $α (G, 𝜀)$ ). Write

α (G, 𝜀) = \max {1 - \frac{| A_{(𝜀 D)} |}{| G |} : A \subseteq G, \frac{| A |}{| G |} \geq \frac{1}{2}} .

So $α (G, 𝜀)$ small says “ $\frac{1}{2}$ -sized sets have large $𝜀 D$ -neighbourhoods”.

Definition (Levy family). Say a sequence of graphs is a Lévy family if $α (G_{n}, 𝜀) \to 0$ as $n \to \infty$ , for each $𝜀 > 0$ .

So Theorem 5 tells us that the sequence $(Q_{n})$ is a Lévy family – even a normal Lévy family, meaning $α (G_{n}, 𝜀)$ grows exponentially small in $n$ , for each $𝜀 > 0$ .

So have concentration of measure for any Lévy family.

Many naturally-occurring families of graphs are Lévy families.

Example. $(S_{n})$ , where $S_{n}$ is made into a graph by joining $σ$ to $σ^{'}$ if $σ^{'} σ^{- 1}$ is a transposition.

Can define $α (X, 𝜀)$ similarly for any metric measure space $X$ (of finite measure and finite diameter).

Example. $(S^{n})$ is a Lévy family.

Two ingredients:

(1) An isoperimetric inequality on $S_{n}$ : for $A \subset S_{n}$ , $C$ a circular cap with $| C | = | A |$ , have $| A N 𝜀 | \geq | C_{(𝜀)} |$ .
Proof by compression:
(2) Estimate: circular cap $C$ of measure $\frac{1}{2}$ is the cap of angle $\frac{π}{2}$ , so $C_{𝜀}$ is the circular cap of angle $\frac{π}{2} + 𝜀$ .

This complement has measure about $\int_{𝜀}^{\frac{π}{2}} \cos^{n - 1} t d t$ , which $\to 0$ as $n \to \infty$ .

We deduced concentration of measure from an isoperimetric inequality.

Conversely:

Proposition 7. Assuming that:

$t$ , $α$ and $G$ are such that for any Lipschitz function $f : G \to ℝ$ with median $M$ we have
$\frac{| {x \in G : | f (x) - M | > t} |}{| G |} \leq α,$

Then for all

A \subseteq G

with

\frac{| A |}{| G |} \geq \frac{1}{2}

, we have

\frac{| A_{(t)} |}{| G |} \geq 1 - α

Proof. The function $f (x) = d (x, A)$ is Lipschitz, and has $0$ as a median, so

\frac{| {x \in G : x \notin A_{(t)}} |}{| G |} \leq α . □

2.2 Edge-isoperimetric inequalities

For a subset $A$ of vertices of a graph $G$ , the edge-boundary of $A$ is

\partial_{e} A = \partial A = {x y \in E : x \in A, y \notin A} .

An inequality of the form: $| \partial A | \geq f (| A |)$ for all $A \subset G$ is an edge-isoperimetric inequality on $G$ .

What happens in $Q_{n}$ ? Given $| A |$ , which $A \subset Q_{n}$ should we take, to minimise $| \partial A |$ ?

Example. $| A | = 4$ in $Q_{3}$ :

This suggests that maybe subcubes are best.

What if $A \subset Q_{n}$ ? with $2^{k} < | A | < 2^{k + 1}$ ? Natural to take $A = P ([k]) \cup {some stuff containing k + 1}$ . Suppose we are in $Q_{4}$ , and considering $| A | > 2^{3}$ , eg $| A | = 12$ . We might take the whole of the bottom layer, and then stuff in the upper layer. Note that the size of the boundary will be the number of up edges (which is $12 - 2^{3}$ , a constant), plus the number of edges in the top layer. So we just want to minimise the number of edges in the top layer, i.e. find $A^{'} \subset Q_{3}$ with $| A^{'} |$ with minimal boundary.

So we define: for $x, y \in Q_{n}$ , $x \neq y$ , say $x < y$ in the binary ordering on $Q_{n}$ if $\max x Δ y \in y$ . Equivalently, $x < y$ if and only if $\sum_{i \in x} 2^{i} < \sum_{i \in y} 2^{i}$ . “Go up in subcubes”.

Example. In $Q_{3}$ : $\emptyset, 1, 2, 12, 3, 13, 23, 123$ .

For $A \subset Q_{n}$ , $1 \leq i \leq n$ , we define the $i$ -binary compression $B_{i} (A) \subset Q_{n}$ by giving its $i$ -sections:

\begin{array}{l} {(B_{i} (A))}_{-}^{(i)} & = initial segment of binary on P (X - i) of size | A_{-}^{(i)} | \\ {(B_{i} (A))}_{+}^{(i)} & = initial segment of binary on P (X - i) of size | A_{+}^{(i)} | \end{array}

so $| B_{i} (A) | = | A |$ . Say $A$ is $i$ -binary compressed if $B_{i} (A) = A$ .

Theorem 8 (Edge-isoperimetric inequality in $Q_{n}$ ). Assuming that:

$A \subset Q_{n}$
let $C$ the initial segment of binary on $Q_{n}$ with $| C | = | A |$

Then

| \partial C | \leq | \partial A |

. In particular: if

| A | = 2^{k}

then

| \partial A | \geq 2^{k} (n - k)

Remark. Sometimes called the “Theorem of Harper, Lindsey, Bernstein & Hart”.

Proof. Induction on $n$ . $n = 1$ trivial.

For $n > 1$ , $A \subset Q_{n}$ , $1 \leq i \leq n$ :

Claim: $| \partial B_{i} (A) | \leq | \partial A |$ .

Proof of claim: write $B$ for $B_{i} (A)$ . .image Have

|∂A| = |∂(A )| +|∂(A )|+ |A ΔA |
◟-◝−◜-◞ ◟--◝+◜-◞ ◟-+◝◜-−◞
downstairs upstairs across

Also

| \partial B | = | \partial (B_{-}) | + | \partial (B_{+}) | + | B_{+} Δ B_{-} | .

Now, $| \partial (B_{-}) | \leq | \partial (A_{-}) |$ and $| \partial (B_{+}) | \leq | \partial (A_{+}) |$ (induction hypothesis). Also, the sets $B_{+}$ and $B_{-}$ are nested (one is contained inside the other), as each is an initial segment of binary on $P (X - i)$ .

Whence we certainly have $| B_{+} Δ B_{-} | \leq | A_{+} Δ A_{-} |$ . So $| \partial B | \leq | \partial A |$ .

Define a sequence $A_{0}, A_{1}, \dots \subset Q_{n}$ as follows: set $A_{0} = A$ . Having defined $A_{0}, \dots, A_{k}$ , if $A_{k}$ is $i$ -binary compressed for all $n$ then stop the sequence with $A_{k}$ . If not, choose $i$ with $B_{i} (A) \neq A$ and put $A_{k + 1} = B_{i} (A_{k})$ . Must terminate, as the function $k \mapsto \sum_{x \in A_{k}} (position of x in binary)$ is strictly decreasing.

The final family $B = A_{k}$ satisfies $| B | = | A |$ , $| \partial B | \leq | \partial A |$ , and $B$ is $i$ -binary compressed for all $i$ .

Note that $B$ need not be an initial segment of binary, for example ${\emptyset, 1, 2, 3} \subset Q_{3}$ .

However:

Lemma 9. Assuming that:

$B \subset Q_{n}$ is $i$ -binary compressed for all $i$
$B$ not an initial segment of binary

Then

B = P (n - 1) - {1, 2, 3, \dots, n - 1} \cup {n}

(“downstairs minus the last point, plus the first upstairs point”).

(Then done, as clearly $| \partial B | \geq | \partial C |$ , since $C = P (n - 1)$ ).

Proof. As $B$ not an initial segment, there exists $x < y$ with $x \notin B$ , $y \in B$ . Then for all $i$ : cannot have $i \in x, y$ , and cannot have $i \notin x, y$ (as $B$ is $i$ -binary compressed).

Thus for each $y \in B$ , there exists at most 1 earlier $x \notin B$ (namely $x = y^{c}$ ). Also for each $x \notin B$ there is at most one later $y \in B$ (namely $y = x^{c}$ ).

Then $x$ and $y$ adjacent (since $y$ is the unique element in $B$ after $x$ , and $x$ is the unique element not in $B$ before $y$ ).

So $B = {z : z \leq y} - {x}$ , where $x$ is the predecessor of $y$ and $y = x^{c}$ .

So must have $y = {n}$ . □

This concludes the proof of Theorem 8. □

Remark. Vital in the proof of Theorem 8, and of Theorem 1, that the extremal sets (in dimension $n - 1$ ) were nested.

The isoperimetric number of a graph $G$ is

i (G) = \min {\frac{| \partial A |}{| A |} : A \subset G, \frac{| A |}{| G |} \leq \frac{1}{2}} .

$\frac{| \partial A |}{| A |}$ is the “average out-degree of $| A |$ ”.

Corollary 10. $i (Q_{n}) = 1$ .

Proof. Taking $A = P (n - 1)$ , we show $i (Q_{n}) \leq 1$ (as $\frac{| \partial A |}{| A |} = \frac{2^{n - 1}}{2^{n}} = \frac{1}{2}$ ).

To show $i (Q_{n}) \geq \frac{1}{2}$ , just need to show that if $C$ is an initial segment of binary with $| C | \leq 2^{n - 1}$ then $| \partial C | \geq | C |$ .

But $C \subset P (n - 1)$ , so certainly $| \partial C | \geq | C |$ . □

2.3 Inequalities in the grid

For any $k = 2, 3, \dots$ , the grid is the graph on ${[k]}^{n}$ in which $x$ is joined to $y$ if for some $i$ we have $x_{j} = y_{j}$ for all $j \neq i$ and $| x_{i} - y_{i} | = 1$ .

“distance is $l_{1}$ -distance”.

Example. ${[4]}^{2}$

Note that for $k = 2$ this is exactly $Q_{n}$ .

Do we have analogues of Theorem 1 and Theorem 8 for the grid?

Starting with vertex-isoperimetric: which sets $A \subset {[k]}^{n}$ (of given size) minimise $| N (A) |$ ?

Example. In ${[k]}^{2}$ :

For $A$ : $| b (A) | \sim r \sim \sqrt{2 | A |}$ .

For $B$ : $| b (B) | = 2 r = 2 \sqrt{| B |}$ .

This suggests we “go up in levels” according to $| x | = \sum_{i = 1}^{n} | x_{i} |$ – e.g. we’d take ${x \in {[k]}^{n} : | x | \leq r}$ .

What if $| {x \in {[k]}^{n} : | x | \leq r} | < | A | < | {x \in {[k]}^{n} : | x | \leq r + 1}$ ?

Guess: take $A = {x \in {[k]}^{n} : | x | \leq r}$ plus some points with $| x | = r + 1$ , but which points?

Example. In ${[k]}^{3}$ :

so “keep $x_{1}$ large”.

This suggests in the simplicial order on ${[k]}^{n}$ , we set $x < y$ if either $| x | < | y |$ or $| x | = | y |$ and $x_{i} > y_{i}$ , where $i = \min, c b j : x_{j} \neq y_{j}}$ .

Note. Agrees with the previous definition of simplicial ordering when $k = 2$ .

Example. On ${[3]}^{2}$ : $(1, 1)$ , $(2, 1)$ , $(1, 2)$ , $(1, 1)$ , $(2, 2)$ , $(1, 3)$ , $(3, 2)$ , $(2, 3)$ , $(3, 3)$ .

On ${[4]}^{3}$ : $(1, 1, 1)$ , $(2, 1, 1)$ , $(1, 2, 1)$ , $(1, 1, 2)$ , $(3, 1, 1)$ , $(2, 2, 1)$ , $(2, 1, 2)$ , $(1, 3, 1)$ , $(1, 2, 2)$ , $(1, 1, 3)$ , $(4, 1, 1)$ , $(3, 2, 1)$ , …

r $A \subset {[k]}^{n}$ ( $n \geq 2$ ), and $1 \leq i \leq n$ , the $i$ -sections of $A$ are the sets $A_{1}, \dots, A_{k}$ (or $A_{1}^{(i)}, \dots, A_{k}^{(i)}$ ) as a subset of ${[k]}^{n - 1}$ defined by:

A_{t} = {x \in {[k]}^{n - 1} : (x_{1}, x_{2}, \dots, x_{i - 1}, t, x_{i}, x_{i + 1}, \dots, x_{n - 1}) \in A},

for each $1 \leq t \leq k$ .

The $i$ -compression of $A$ is $C_{i} (A) \subset {[k]}^{n}$ is defined by giving its $i$ -sections:

C_{i} {(A)}_{t} = initial segment of {[k]}^{n - 1} of size | A_{t} |, for each 1 \leq t \leq k .

Thus $| C_{i} (A) | = | A |$ .

Say $A$ is $i$ -compressed if $C_{i} (A) = A$ .

Theorem 11 (Vertex-isoperimetric inequality in the grid). Assuming that:

$A \subset {[k]}^{n}$
$C$ is the initial segment of simplicial order on ${[k]}^{n}$ with $| C | = | A |$

Then

| N (C) | \leq | N (A) |

. In particular, if

| A | \geq | {x : | x | \leq r} |

then

| N (A) | \geq | {x : | x | \leq r + 1} |

Proof. Induction on $n$ . For $n = 1$ it is trivial: if $A \subset {[k]}^{1} \neq \emptyset, {[k]}^{1}$ , then $| N (A) | \geq | A | + 1 = | N (C) |$ .

Given $n > 1$ and $A \subset {[k]}^{n}$ : fix $1 \leq i \leq n$ .

Claim: $| N (C_{i} (A) | \leq | N (A) |$ .

Proof of claim: write $B$ for $C_{i} (A)$ . For any $1 \leq t \leq k$ , we have

N {(A)}_{t} = \underset{from x_{i} = t}{\underset{⏟}{N (A_{t})}} \cup \underset{from x_{i} = t - 1}{\underset{⏟}{A_{t - 1}}} \cup \underset{from x_{i} = t + 1}{\underset{⏟}{A_{t + 1}}} .

(where $A_{0}, A_{k + 1} = \emptyset$ ).

Also,

N {(B)}_{t} = N (B_{t}) \cup B_{t - 1} \cup B_{t + 1} .

Now, $| B_{t - 1} | = | A_{t - 1} |$ and $| B_{t + 1} | = | A_{t + 1} |$ , and $| N (B_{t}) | \leq | N (A_{t}) |$ (induction hypothesis). But the sets $B_{t - 1}$ , $B_{t + 1}$ , $N (B_{t})$ are nested (as each is an initial segment of simplicial order on ${[k]}^{n - 1}$ ).

Hence $| N {(B)}_{t} | \leq | N {(A)}_{t} |$ for each $t$ . Thus $| N (B) | \leq | N (A) |$ .

Among all $B \subset {[k]}^{n}$ with $| B | = | A |$ and $| N (B) | \leq | N (A) |$ , pick one that minimises the quantity $\sum_{x \in B} position of x in simplicial order$ .

Then $B$ is $i$ -compressed for all $i$ . Note however, that this time we will make use of this minimality property of $B$ for more than just deducing that $B$ is $i$ -compressed for all $i$ .

Case 1: $n = 2$ . What we know is precisely that $B$ is a down-set ( $A \subset {[k]}^{n}$ is a down-set if $x \in A$ , $y_{i} \leq x_{i} \forall i ⟹ y \in A$ )

Let $r = \min {| x | : x \notin B}$ and $s = \max {| x | : x \notin B}$ . May assume $r \leq s$ , since $r = s + 1$ implies $B = {x : | x | \leq r - 1}$ would imply $B = C$ .

If $r = s$ : then ${x : | x | \leq r - 1} \subset B \subset {x : | x | \leq r}$ . So clearly $| N (B) | \geq | N (C) |$ .

If $r < s$ : cannot have ${x : | x | = s} \subset B$ , because then also ${x : | x | = r} \subset B$ (as $B$ is a down-set).

So there exists $y, y^{'}$ with $| y | = | y^{'} | = s$ , $y \in B$ , $y^{'} \notin B$ and $y^{'} = y \pm (e_{1} - e_{2})$ ( $e_{1} = (1, 0)$ , $e_{2} = (0, 1)$ ).

Similarly, cannot have ${x : | x | = r} \cap B = \emptyset$ , because then ${x : | x | = s} \cap B = \emptyset$ (as $B$ is a down-set). So there exists $x, x^{'}$ with $| x | = | x^{'} | = r$ , $x \notin B$ , $x^{'} \in B$ and $x^{'} = x \pm (e_{1} - e_{n})$ . Now let $B^{'} = B \cup {x} - {y}$ . From $B$ we lost $\geq 1$ point in the neighbourhood (namely $z$ in the picture), and gained $\leq 1$ point (the only point that we can possibly gain is $w$ ), so $| N (B^{'}) | \leq | N (B) |$ . This contradicts minimality of $B$ . This finishes the two dimensional case.

Case 2: $n \geq 3$ . For any $1 \leq i \leq n - 1$ and any $x \in B$ with $x_{n} > 1$ , $x_{i} < k$ . Have $x - r_{n} + e_{i} \in B$ (as $B$ is $j$ -compressed for any $j$ , so apply with some $j \neq i, n$ ). So, considering the $n$ -sections of $B$ , we have $N (B_{t}) \subset B_{t - 1}$ for all $t = 2, \dots, k$ .

Recall that $N {(B)}_{t} = N (B_{t}) \cup B_{t + 1} \cup B_{t - 1}$ . So in fact $N {(B)}_{t} = B_{t - 1}$ for all $t \geq 2$ . Thus

| N (B) | = \underset{level k}{\underset{⏟}{| B_{k - 1} |}} + \underset{level k - 1}{\underset{⏟}{| B_{k - 2} |}} + \dots + \underset{level 2}{\underset{⏟}{| B_{1} |}} + \underset{level 1}{\underset{⏟}{| N (B_{1}) |}} = | B | - | B_{k} | + | N (B_{1}) | .

Similarly,

| N (C) | = | C | - | C_{k} | + | N (C_{1}) | .

So to show $| N (C) | \leq | N (B) |$ , enough to show that $| B_{k} | \leq | C_{k} |$ and $| B_{1} | \geq | C_{1} |$ .

$| B_{k} | \leq | C_{k} |$ : define a set $D \subset {[k]}^{n}$ as follows: put $D_{k} = B_{k}$ , and for $t = k - 1, k - 2, \dots, 1$ set $D_{t} = N (D_{t - 1})$ . Then $D \subset B$ , so $| D | \leq | B |$ . Also, $D$ is an initial segment of simplicial order. So in fact $D \subset C$ , whence $| B_{k} | = | D_{k} | \leq | C_{k} |$ .

$| B_{1} | \geq | C_{1} |$ : define a set $E \subset {[k]}^{n}$ as follows: put $E_{1} = B_{1}$ and for $t = 2, 3, \dots, k$ set $E_{t} = {x \in {[k]}^{n - 1} : N ({x}) \subset E_{t - 1}}$ ( $E_{t}$ is the biggest it could be given $N (E_{t}) \subset E_{t}$ ). Then $E \supset B$ , so $| E | \geq | B |$ . Also, $E$ is an initial segment of simplicial order. So $E \supset C$ , whence $| B_{1} | = | E_{1} | \geq | C_{1} |$ . □

Corollary 12. Let $A \subset {[k]}^{n}$ with $| A | \geq | {x : | x | \leq n} |$ . Then $| A_{(t)} | \geq | {x : | x | \leq r + t} |$ for all $t$ .

Remark. Can check from Corollary 12 that, for $k$ fixed, the sequence ${({[k]}^{n})}_{n = 1}^{\infty}$ is a Lévy family.

2.4 The edge-isoperimetric inequality in the grid

Which set $A \subset {[k]}^{n}$ (of given size) should we take to minimise $| \partial A |$ ?

Example. In ${[k]}^{n}$ :

Suggests squares are best.

However...

So we have “phase transitions” at $| A | = \frac{k^{2}}{4}$ and $\frac{3 k^{2}}{4}$ – extremal sets are not nested. This seems to rule out all our compression methods.

And in ${[k]}^{3}$ ?

\begin{array}{l} {[a]}^{3} (cube) & ⇝ {[a]}^{2} \times [k] (square column) \\ ⇝ [a] \times {[k]}^{2} (half space) \\ ⇝ complement of square column \\ ⇝ complement of cube \end{array}

So in ${[k]}^{n}$ , up to $| A | = \frac{k^{n}}{2}$ , we get $n - 1$ of these phase transitions!

Note that if $A = [a] \times {[k]}^{n - d}$ . Then $| \partial A | = d a^{d - 1} k^{n - d} = d | A |^{1 - \frac{1}{d}} k^{\frac{n}{d} - 1}$ .

Theorem 13. Assuming that:

$A \subset {[k]}^{n}$
$| A | \leq \frac{k^{n}}{2}$

Then

| \partial A | \geq \min {d | A |^{1 - \frac{1}{d}} k^{\frac{n}{d} - 1} : 1 \leq d \leq n} .

“Some set of the form ${[a]}^{d} \times {[k]}^{n - d}$ is best.”

Called the “edge-isoperimetric inequality in the grid”.

The following discussion is non-examinable (until told otherwise).

Proof (sketch). Induction on $n$ . $n = 1$ is trivial.

Given $A \subset {[k]}^{n}$ with $| A | \leq \frac{k^{n}}{2}$ , where $n > 1$ :

Wlog $A$ is a down-set (just down-compress, i.e. stamp on your set in direction $i$ for each $i$ ). For any $1 \leq i \leq n$ , define $C_{i} (A) \subset {[k]}^{n}$ by giving its $i$ -sections:

C_{i} {(A)}_{t} = extremal set of size | A_{t} | in {[k]}^{n - 1},

which will be a set of the form ${[a]}^{d} \times {[k]}^{n - 1 - d}$ , or a complement. Write $B = C_{i} (A)$ . Do we have $| \partial B | \leq | \partial A |$ ?

Now, $A$ is a down-set, so

| \partial A | = \underset{horizontal edges}{\underset{⏟}{| \partial A_{1} | + \dots + | \partial A_{k} |}} + \underset{vertical edges}{\underset{⏟}{| A_{1} | - | A_{k} |}}

and

| \partial B | = | \partial B_{1} | + \dots + | \partial B_{k} | + ?

The $?$ is because $B$ not a down-set, as extremal sets in dimension $n - 1$ are not nested.

Indeed, can have $| \partial B | > | \partial A |$ :

Idea: try to introduce a “fake” boundary $\partial^{'}$ : want $\partial^{'} A \leq \partial A$ , with $\partial^{'} = \partial$ on extremal sets, such that $C_{i}$ does decrease $\partial^{'}$ (then done).

Try $\partial^{'} A = \sum_{t} | \partial A_{t} | + | A_{1} | - | A_{k} |$ . Then $\partial^{'} A \leq | \partial A |$ for all $A$ , equality for extremal sets (as equality for any down-set) and $\partial^{'} C_{i} (A) \leq \partial^{'} A$ . But: fails for $C_{j} (A)$ for all $j \neq i$ .

Could try to fix this by defining $\partial^{″} A = \sum_{i} (| A_{1}^{(i)} | - | A_{k}^{(i)} |)$ . Also fails – for example if $A$ is the “outer shell” of ${[k]}^{n}$ then $\partial^{″} A = 0$ .

So far, have

\begin{array}{l} | \partial A | & \geq \partial^{'} A \\ \geq \partial^{'} B \\ = \sum_{t} | \partial B_{t} | + | B_{1} | - | B_{k} | \\ = \sum_{t} f (| B_{t} |) + | B_{1} | - | B_{k} | \end{array}

where $f$ is the extremal function in ${[k]}^{n - 1}$ .

Now, $f$ is the pointwise minimum of some functions of the form $c x^{1 - \frac{1}{d}}$ and $c {(k^{n - 1} - x)}^{1 - \frac{1}{d}}$ – each of which is a concave function. Hence $f$ itself is a concave function.

Consider varying $| B_{2} |, \dots, | B_{k - 1} |$ , keeping $| B_{2} | + \dots + | B_{k - 1} |$ constant and keeping $| B_{1} | \geq | B_{2} | \geq \dots \geq | B_{k - 1} | \geq | B_{k} |$ .

We obtain $\partial^{'} B \geq \partial^{'} C$ , where for some $λ$ ,

C_{t} = {\begin{matrix} B_{1} & \forall 1 \leq t \leq λ \\ B_{k} & \forall λ + 1 \leq t \leq k \end{matrix}

So:

\begin{array}{l} | \partial A | & = \partial^{'} A \\ \geq \partial^{'} B \\ \geq \partial^{'} C \\ = λ f (| B_{1} |) + (k - λ) f (| B_{k} |) + | B_{1} | - | B_{k} | \end{array}

but $C$ is still not a down-set.

Now vary, $| B_{1} |$ , keeping $λ | B_{1} | + (k - λ) | B_{k} |$ fixed ( $λ$ fixed) and $| B_{1} | \geq | B_{k} |$ .

This is a concave function of $| B_{1} |$ – as concave + concave + linear. Hence “make $| B_{1} |$ as small or large as possible”.

i.e. $\partial^{'} C \geq \partial^{'} D$ , where one of the following holds:

$D_{t} = D_{1}$ for all $t$
$D_{t} = D_{1}$ for all $t \leq λ$ , $D_{t} = \emptyset$ for all $t > λ$
$D_{t} = {[k]}^{n - 1}$ for all $t \leq λ$ , $D_{t} = D_{k}$ for all $t > λ$ .

But (miraculously), this $D$ is a down-set!

Hence

| \partial A | = \partial^{'} A \geq \partial^{'} B \geq \partial^{'} C \geq \partial^{'} D = | \partial D | .

So our “compression in direction $i$ ” is: $A \mapsto D$ .

Now finish as before. □

Remark. To make this precise, work instead in ${[0, 1]}^{n}$ (and then take a discrete approximation at the end).

End of non-examinable discussion.

Remark. Very few isoperimetric inequalities are known (even approximately).

For example, “isoperimetric in a layer” – in the graph $X^{(r)}$ , with $x, y$ joined if $| x \cap y | = r - 1$ (i.e. $d (x, y) = 2$ in $Q_{n}$ ).

This is open. Nicest special case is $r = \frac{n}{2}$ , where it is conjectured that balls are best – i.e. sets of the form ${x \in {[r]}^{(r)} : | x \cap [r] | \geq t}$ .