Extremal Combinatorics

I.B. Leader

Michaelmas 2004

1 Isoperimetric Inequalities

“Given the size of a set, how small can its boundary be?” For example,

• in ℝ^{2}, circular discs are best;

• in ℝ^{3}, spherical balls are best;

• in S^{2} ⊂ ℝ^{3}, ‘circular caps’ are best.

For a fixed graph G and any set A ⊂ V (G), the boundary of A is the set

b(A) = {x ∈ V (G) − A : x ∼ y for some y ∈ A}.

Given |A|, how do we minimize |b(A)|? An isoperimetric inequality on G is an inequality of the form

A ⊂ V (G), |A| = m ⟹ |b(A)| ≥ f(m)

for some function f. Equivalently, we wish to minimize the neighbourhood N(A) of A, where N(A) = A ∪ b(A).

A good candidate for a set with small boundary is a ball, i.e. a set of the form B(x, r) = {y ∈ G : d(x, y) ≤ r} where d(x, y) denotes the usual graph distance (the length of a shortest x-y path).

1.1 The Discrete Cube

Let X be a set. A set system on X is a collection A ⊂ PX of subsets of X. Usually we take X = [n] = {1, 2, …, n}. An example of a set system on X is X^{(r)} = {A ⊂ X : |A| = r}.

Make PX into a graph by joining A to B if B = A ∪ {i} for some i ∉ A (or vice versa). This graph is the discrete cube Q_{n}.

If we identify each A ∈ Q_{n} with a 01-sequence of length n (for example, in Q_{3} we make the identification ∅ ↔ 000, {1} ↔ 100, {2, 3} ↔ 011 etc.) then Q_{n} is identified with the unit cube in ℝ^{n}. Then X^{(r)} (the family of all r-sets) is just a ‘slice’ through Q_{n}.

Which sets in Q_{n} have the smallest boundaries? In general, it seems that balls X^{(≤r)} = B(∅, r) = X^{(0)} ∪ X^{(1)} ∪ ⋯ ∪ X^{(r)} are best. But what if |A| is not the exact size of a ball?

A little experimentation suggests that if |X^{(<r)}| < |A| < |X^{(≤r)}| then it is best to take A to be X^{(<r)} together with an initial segment of the lex order on X^{(r)}. (The lexicographic or lex or dictionary order on X^{(r)} is defined by: if x = {a_{1}, a_{2}, …, a_{r}} (a_{1} < a_{2} < ⋯ < a_{r}) and y = {b_{1}, b_{2}, …, b_{r}} (b_{1} < b_{2} < ⋯ < b_{r}) then x < y if a_{1} < b_{1}, or a_{1} = b_{1} and a_{2} < b_{2}, or … or a_{1} = b_{1}, a_{2} = b_{2}, …, a_{r−1} = b_{r−1} and a_{r} < b_{r}. Equivalently, x < y if a_{s} < b_{s} where s = min{t : a_{t} ≠ b_{t}}. For example, the lexicographic order on [4]^{(2)} is 12, 13, 14, 23, 24, 34.)

The simplicial ordering on Q_{n} is defined by x < y if |x| < |y| or |x| = |y| and x < y in lex. For example,

• on Q_{3}: ∅, 1, 2, 3, 12, 13, 23, 123;

• on Q_{5}: ∅, 1, 2, 3, 4, 5, 12, 13, 14, 15, 23, 24, 25, 34, 35, 45, 123, 124, 125, 134, 135, 145, 234, 235, 245, 345, 1234, 1235, 1245, 1345, 2345, 12345.

Theorem 1 (Harper’s Theorem). Let A ⊂ Q_{n} and let C be the first |A| points of Q_{n} in the simplicial order. Then |N(A)| ≥ |N(C)|. In particular, if |A| ≥ ∑_{i=0}^{r} \binom{n}{i} then |N(A)| ≥ ∑_{i=0}^{r+1} \binom{n}{i}.

Remarks. A Hamming ball is a set A with X^{(<r)} ⊂ A ⊂ X^{(≤r)} for some r. If we knew A was a Hamming ball then we would be done by Kruskal-Katona (which says that to minimize the upper shadow ∂^{+}A of a family A ⊂ X^{(r)}, where ∂^{+}A = {y ∈ X^{(r+1)} : y ⊃ x for some x ∈ A}, take A to be an initial segment of lex). And, conversely, Theorem 1 implies Kruskal-Katona: given A ⊂ X^{(r)}, apply the theorem to X^{(<r)} ∪ A. The main idea is that of ‘compressions’. We try to transform A → A′ such that

• |A′| = |A|;

• |N(A′)| ≤ |N(A)|; and

• A′ looks more like C than A did.

Ideally, we transform repeatedly A → A′ → A′′ → ⋯, ending up with a family B so similar to C that we can see directly that |N(B)| ≥ |N(C)|.

For A ⊂ Q_{n} and 1 ≤ i ≤ n, the i-sections of A are the set-systems A_{+} = A_{+}^{(i)} and A_{−} = A_{−}^{(i)} in P(X − i) given by

A_{+} = {x ∈ P(X − i) : x ∪ i ∈ A}

and

A_{−} = {x ∈ P(X − i) : x ∈ A}.

For example, in Q_{4} the family A = {12, 13, 23, 124, 134} has A_{−}^{(3)} = {12, 124} and A_{+}^{(3)} = {1, 2, 14}.

The i-compression or codimension-1 i-compression of A is the system C_{i}(A) ⊂ Q_{n} defined by |C_{i}(A)_{+}| = |A_{+}|, |C_{i}(A)_{−}| = |A_{−}|, and C_{i}(A)_{+} and C_{i}(A)_{−} are initial segments of the simplicial order on P(X − i). Note that |C_{i}(A)| = |A|. Say A ⊂ Q_{n} is i-compressed if C_{i}(A) = A.

Proof (of Theorem 1). The proof is by induction on n; the case n = 1 is trivial. Claim. If A ⊂ Q_{n} and 1 ≤ i ≤ n then |N(C_{i}(A))| ≤ |N(A)|. Proof of claim. Write B for C_{i}(A). We have

|N(A)| = |N(A_{+}) ∪ A_{−}| + |N(A_{−}) ∪ A_{+}|

and

|N(B)| = |N(B_{+}) ∪ B_{−}| + |N(B_{−}) ∪ B_{+}|.

Now |B_{−}| = |A_{−}| and |N(B_{+})| ≤ |N(A_{+})| (by the induction hypothesis). Also, B_{−} is an initial segment of the simplicial order. And so is N(B_{+}) (because the neighbourhood of an initial segment of the simplicial order is itself an initial segment of the simplicial order).

Hence B_{−} and N(B_{+}) are nested (i.e. one is contained in the other), and so we have |N(B_{+}) ∪ B_{−}| ≤ |N(A+) ∪ A_{−}|. Similarly, we also have |N(B_{−}) ∪ B_{+}| ≤ |N(A_{−}) ∪ A_{+}|. // Define a sequence A_{0}, A_{1}, A_{2}, … ⊂ Q_{n} as follows: set A_{0} = A. Having defined A_{0}, A_{1}, …, A_{k}, if A_{k} is i-compressed for all i then stop the sequence with A_{k}. Otherwise, there exists i with A_{k} not i-compressed; set A_{k+1} = C_{i}(A_{k}) and continue. This process must terminate since ∑_{x∈A_{k}} f(x) (where f(x) denotes the position of x in the simplicial order on Q_{n}) is a decreasing function of k. Thus we have B ⊂ Q_{n} such that

• |B| = |A|; • |N(B)| ≤ |N(A)|; and

• B is i-compressed for all i.

So, must a set that is i-compressed for all i be an initial segment of the simplicial order? (If so then we are done, as B = C.) Unfortunately, the answer is no; for example, take {∅, 1, 2, 12} ⊂ Q_{3}. However, if B ⊂ Q_{n} is i-compressed for all i and is not an initial segment of the simplicial order then EITHER n is odd, say n = 2k + 1, and

B = X^{(≤k)} ∪ {12 … (k + 1)} − {(k + 2)(k + 3) … (2k + 1)}

OR n is even, say n = 2k, and

B = X^{(<k)} ∪ {x ∈ X^{(k)} : 1 ∈ X} ∪ {23 … (k + 1)} − {1(k + 2)(k + 3) … (2k)}

(by Lemma 2 below).

Having proved Lemma 2, the proof of Theorem 1 will be complete as in each case it is clear that |N(B)| ≥ |N(C)|.

Lemma 2. Let B ⊂ Q_{n} be i-compressed for all i but not an initial segment of the simplicial order. Then EITHER n is odd, say n = 2k + 1, and

B = X^{(≤k)} ∪ {12 … (k + 1)} − {(k + 2)(k + 3) … (2k + 1)}

OR n is even, say n = 2k, and

B = X^{(<k)} ∪ {x ∈ X^{(k)} : 1 ∈ X} ∪ {23 … (k + 1)} − {1(k + 2)(k + 3) … (2k)}.

Proof. As B is not an initial segment of the simplicial order, we have some x < y with x ∉ B and y ∈ B. Fix 1 ≤ i ≤ n: can we have i ∈ x and i ∈ y? No, as B is i-compressed. Similarly, we cannot have i ∉ x and i ∉ y. So i ∈ x△y for any i. Thus y = x^{c}.

So for each y ∈ B, at most one x < y has x ∉ B (namely x = y^{c}); and for each x ∉ B, at most one y > x has y ∈ B (namely y = x^{c}). Thus B = {z ∈ Q_{n} : z ≤ y} − {x} for some y, where x is the predecessor of y and x = y^{c}. Which x ∈ Q_{n} have x^{c} the successor of x? If n is odd then x must be the last point of X^{(≤(n−1)/2)}. If n is even then x must be the last point of X^{(n/2)} containing a 1.

Remarks. 1. We can also prove Theorem 1 by generalizing UV -compressions (allowing |U| < |V |).

2. This proof also proves the Kruskal-Katona theorem directly (if desired).

For A ⊂ Q_{n} and t = 0, 1, 2, …, the t-neighbourhood of A is the set A_{(t)} = {x ∈ Q_{n} : d(x, A) ≤ t}. So, for example, A_{(1)} is just N(A).

Corollary 3. Let A ⊂ Q_{n} with |A| ≥ ∑_{i=0}^{r} \binom{n}{i}. Then for any t = 0, 1, 2, …, we have |A_{(t)}| ≥ ∑_{i=0}^{r+t} \binom{n}{i}.

Proof. If |A_{(t)}| ≥ ∑_{i=0}^{r+t} \binom{n}{i} then |A_{(t+1)}| ≥ ∑_{i=0}^{r+t+1} \binom{n}{i} by Harper’s Theorem, so we are done by induction.

To see the strength of Corollary 3, we need an estimate on the tail of the binomial distribution.

Lemma 4. For 0 < ε < 1/4 we have

∑_{i=0}^{⌊(1/2−ε)n⌋} \binom{n}{i} ≤ \frac{1}{ε}e^{−ϵ^{2}n/2}2^{n}.

Note. This is an exponentially small function of 2^{n} (for ε fixed).

Proof. We have \binom{n}{k−1} = \binom{n}{k} · \frac{k}{n−k+1}, so for k ≤ (1/2 − ε) n we have

\begin{matrix}( & {n \atop k−1} & ) \\ ( & {n \atop k} & ) \end{matrix} ≤ \frac{(1/2 − ε) n}{(1/2 + ε) n} = 1 − \frac{2ε}{1/2 + ε} ≤ 1 − 2ε

and so

∑_{n=0}^{⌊(1/2−ε)n⌋} \binom{n}{i} ≤ \frac{1}{2ε}\binom{n}{⌊(1/2 − ε) n⌋}

(sum of a geometric progression). Similarly,

\binom{n}{⌊(1/2 − ε) n⌋} ≤ \binom{n}{⌊((1 − ε)/2) n⌋} (1 − ε)^{εn/2−1} ≤ 2^{n} · 2 · e^{−ε^{2}n/2}

(as 1 − ε ≤ e^{−ε}), and so

∑_{i=0}^{⌊(1/2−ε)n⌋} \binom{n}{i} ≤ \frac{1}{2ε} · 2^{n} · 2 · e^{−ε^{2}n/2}.

Combining this with the isoperimetric inequality:

Theorem 5. Let A ⊂ Q_{n} and 0 < ε < \frac{1}{4}. Then

\frac{|A|}{2^{n}} ≥ \frac{1}{2} ⟹ \frac{|A_{(εn)}|}{2^{n}} ≥ 1 − \frac{1}{ε}e^{−ε^{2}n/2}.

Proof. We have |A| ≥ ∑_{i=0}^{⌈n/2−1⌉} \binom{n}{i} and so |A_{(εn)}| ≥ ∑_{i=0}^{⌈n/2−1+εn⌉} \binom{n}{i}. Thus

|A_{(εn)}^{c}| ≤ ∑_{i=⌈n/2+εn⌉}^{n} \binom{n}{i} = ∑_{i=0}^{⌊n/2−εn⌋} \binom{n}{i} ≤ \frac{1}{ε}e^{−ε^{2}n/2} · 2^{n}.

Remarks. 1. This says that “half-sized sets have exponentially large εnneighbourhoods”.

2. The same proof gives that

\frac{|A|}{2^{n}} ≥ \frac{1}{ε}e^{−ε^{2}n/2} ⟹ \frac{|A_{(2εn)}|}{2^{n}} ≥ 1 − \frac{1}{ε}e^{−ε^{2}n/2}.

1.2 Concentration of Measure

A function f: Q_{n} → ℝ is Lipschitz (with constant 1) if |f(x) − f(y)| ≤ 1 whenever x and y are adjacent. We say that M ∈ ℝ is a median of f if |{x : f(x) ≤ m}| ≥ 2^{n−1} and |{x : f(x) ≥ m}| ≥ 2^{n−1}.

We are now ready to show that “well-behaved” functions on Q_{n} are roughly constant.

Theorem 6. Let f: Q_{n} → ℝ be Lipschitz with median M. Then for 0 < ε < \frac{1}{4} we have

\frac{|\{x : |f(x) − M| ≤ εn\}|}{2^{n}} ≥ 1 − \frac{2}{ε}e^{− \frac{ε^{2}n}{2}} .

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

Proof. Let A = {x ∈ Q_{n} : f(x) ≤ M}. Then |A|/2^{n} ≥ 1/2, so, by Theorem 5, |A_{(εn)}| ≥ 1 − \frac{1}{ε}e^{−ε^{2}n/2}. But if x ∈ A_{(εn)} then f(x) ≤ M + εn (as f is Lipschitz), so

\frac{|\{x : f(x) ≤ M + εn\}|}{2^{n}} ≥ 1 − \frac{1}{ε}e^{−ε^{2}n/2}.

Similarly,

\frac{|\{x : f(x) ≥ M − εn\}|}{2^{n}} ≥ 1 − \frac{1}{ε}e^{−ε^{2}n/2}

and so

\frac{|\{x : M − εn ≤ f(x) ≤ M + εn\}|}{2^{n}} ≥ 1 − \frac{2}{ε}e^{−ε^{2}n/2}.

Let G be a graph of diameter D, i.e. such that D = max{d(x, y) : x, y ∈ G}. For ε > 0, write

α(G, ε) = max \{1 − \frac{|A_{(εD)}|}{|G|} : A ⊂ G, \frac{|A|}{|G|} ≥ \frac{1}{2}\} .

So “α(G, ε) small means half-sized sets have large neighbourhoods”. A sequence G_{1}, G_{2}, G_{3}, …, of graphs is called a Lévy family if α(G_{n}, ε) → 0 as n → ∞ for each ε > 0. So Theorem 5 tells us that (Q_{n})_{n=1}^{∞} forms a Lévy family, in fact a normal Lévy family, meaning that α(G, ε) is exponentially small in n for each ε > 0.

An analogue of Theorem 6 shows that any Lévy family exhibits concentration of measure.

Remarkably, many natural families of graphs are normal Lévy families— for example, the permutation group S_{n} where σ and τ are adjacent if στ^{−1} is a transposition.

We can also define α(G, ε) for G any metric measure space (of finite diameter and finite measure). It turns out that many natural families of spaces are Lévy families—for example, the spheres S^{n}. This is from the isoperimetric inequality on the sphere, together with the fact that ∫_{ε}^{1} cos^{n} x dx → 0 as n → ∞ for each ε > 0.

We deduced concentration of measure from the isoperimetric inequality. Conversely:

Proposition 7. Let G be a connected graph, t > 0 and α > 0, and suppose that any Lipschitz function f on G with median M has

|{x ∈ G : |f(x) − M| > t}| ≤ α|G|.

Then for all A ⊂ G,

\frac{|A|}{|G|} ≥ \frac{1}{2} ⟹ \frac{|A_{(t)}|}{|G|} ≥ 1 − α.

Proof. Given A ⊂ G with |A|/|G| ≥ 1/2, let f(x) = d(x, A). Then f is Lipschitz and has 0 as a median so |{x ∈ G : d(x, A) > t}| ≤ α|G|, as required.

1.3 Edge-Isoperimetric Inequalities

For a graph G and a set A ⊂ V (G), the edge-boundary of A is the set

∂A = {xy ∈ E(G) : x ∈ A, y ∉ A},

i.e. “the edges leaving A”. An edge-isoperimetric inequality on G is an inequality of the form

A ⊂ G, |A| = m ⟹ |∂A| ≥ f(M)

for some function f.

What happens in the cube? For example, in Q_{3} with |A| = 4: if A is an initial segment in the simplicial order then |∂A| = 6; but if A is a codimension-1 subcube then |∂A| = 4.

Experiment suggests that if |A| = 2^{k} then it is best to take A to be a k-dimensional subcube (say P[k]); while if, say, |A| > 2^{n−1} then take P[n−1] together with some of the rest of the cube.

Say x < y in the binary ordering on Q_{n} if max(x△y) ∈ y, or equivalently if ∑_{i∈x} 2^{i} < ∑_{i∈y} 2^{i}. For example, the binary ordering on Q_{3} is ∅, 1, 2, 12, 3, 13, 23, 123.

Our aim is to show that initial segments in the binary order minimize |∂A|.

For A ⊂ Q_{n} and 1 ≤ i ≤ n, the i-binary-compression of A is the setsystem B_{i}(A) ⊂ Q_{n} defined by |B_{i}(A)_{+}| = |A_{+}|, |B_{i}(A)_{−}| = |A_{−}| and B_{i}(A)_{+}, B_{i}(A)_{−} are initial segments of the binary order on P(X − i).

Theorem 8 (Edge-isoperimetric inequality in the cube). Let A ⊂ Q_{n} and let C be the first |A| points in the binary order on Q_{n}. Then |∂A| ≥ |∂C|. In particular, if |A| = 2^{k} then |∂A| ≥ (n − k)2^{k}.

Remark. This is sometimes called the Theorem of Harper, Lindsey, Bernstein and Hart.

Proof. The proof is by induction on n; the case n = 1 is trivial. Claim. For any A ⊂ Q_{n} and 1 ≤ i ≤ n we have |∂B_{i}(A)| ≤ |∂A|. Proof of claim. Write B for B_{i}(A). Then for the set-systems A and B, we have |∂A| = |∂A_{−}|+|∂A_{+}|+|A_{−}△A_{+}| and |∂B| = |∂B_{−}|+|∂B_{+}|+|B_{−}△B_{+}|. Now, |∂B_{−}| ≤ |∂A_{−}| and |∂B_{+}| ≤ |∂A_{+}| (by the induction hypothesis). Also, |B_{+}| = |A_{+}|, |B_{−}| = |A_{−}| and B_{+}, B_{−} are nested (as each is an initial segment of the binary order), so |B_{+}△B_{−}| ≤ |A_{+}△A_{−}|. Thus |∂B| ≤ |∂A|. // Define A_{0}, A_{1}, A_{2}, … in Q_{n} as follows. Set A_{0} = A. Having defined A_{0}, A_{1}, …, A_{k}, if A_{k} is i-binary-compressed for all i then stop. If not, we have B_{i}(A_{k}) ≠ A_{k} for some i; set A_{k+1} = B_{i}(A_{k}) and continue.

This must end with some A_{k}, as otherwise the sequence ∑_{x∈A_{k}} g(x), where g(x) denotes the position of x in the binary order, is decreasing in k. The set system B = A_{k} satisfies |B| = |A|, |∂B| ≤ |∂A| and B_{i}(B) = B for all i. Must B be an initial segment of the binary order? No, for example B = {∅, 1, 2, 3} in Q_{3}. However, if B is not an initial segment of the binary order then we must have B = P[n − 1] ∪ {n} − {123 … (n − 1)} (by Lemma 9 below), and it is clear in this case that |∂B| ≥ |∂C|.

Lemma 9. Let B ⊂ Q_{n} be i-binary-compressed for all i but not an initial segment of the binary order. Then B = P[n − 1] ∪ {n} − {123 … (n − 1)}.

Proof. We have x ∉ B and y ∈ B for some x, y ∈ Q_{n} with x < y in the binary order. As in the proof of Lemma 2, we must have x = y^{c}, so that B = {z : z ≤ y in binary}∪{x}, where x is the predecessor of y in the binary order and x = y^{c}. Hence x is the last point with n ∉ x and y is the first point with n ∈ y.

Remarks. 1. It was vital for the proof that the extremal sets formed a nested family (to get |B_{+}△B_{−}| ≤ |A_{+}△A_{−}|).

2. The proof was routine, given the idea of codimension-1 compressions.

The isoperimetric number of a connected graph G is defined by

i(G) = min \{\frac{|∂A|}{|A|} : A ⊂ V (G), |A| ≤ \frac{1}{2}|V (G)|\} ,

so “i(G) large means half-size sets have large out-degree”.

Corollary 10. The cube Q_{n} has isoperimetric number 1.

Proof. For any C an initial segment of the binary order with |C| ≤ 2^{n−1}, we have C ⊂ P[n − 1] so that certainly |∂C| ≥ |C|. Hence any A ⊂ Q_{n} with |A| ≤ 2^{n−1} has |∂A| ≥ |A| (by Theorem 8). Thus i(Q_{n}) ≥ 1. The set P[n−1] shows that i(Q_{n}) ≤ 1.

1.4 Inequalities in the grid

For any k = 2, 3, 4, … and n = 1, 2, 3, …, the grid or grid graph [k]^{n} has vertex set [k]^{n} with x = (x_{1}, x_{2}, …, x_{n}) adjacent to y = (y_{1}, y_{2}, …, y_{n}) if for some i we have |x_{i} − y_{i}| = 1 and x_{j} = y_{j} for all j ≠ i. So [k]^{n} is a ‘product’ of n paths of order k.

Do Theorems 1 and 8 generalize to the grid? (Note that the case k = 2 is Q_{n}.)

1.4.1 Vertex-isoperimetric inequalities in the grid

To minimize the vertex-boundary of a set in the grid, it seems best to take sets of the form {x : |x| ≤ r}, where |x| = x_{1} + x_{2} + ⋯ + x_{n}. The simplicial order on [k]^{n} is defined by x < y if |x| < |y|, or |x| = |y| and x_{1} > y_{1}, or |x| = |y| and x_{1} = y_{1} and x_{2} > y_{2}, or … or |x| = |y| and x_{1} = y_{1} and x_{2} = y_{2} and … and x_{n−2} = y_{n−2} and x_{n−1} > y_{n−1}. Equivalently, x < y if |x| < |y|, or |x| = |y| and x_{s} > y_{s} where s = min{t : x_{t} ≠ y_{t}}. For example:

• on [3]^{2}: (1, 1), (2, 1), (1, 2), (3, 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), (3, 1, 2), (2, 3, 1), . . ..

Note that this agrees with the previous definition for k = 2.

Our aim is to show that initial segments of the simplicial order minimize the neighbourhood.

For A ⊂ [k]^{n} and 1 ≤ i ≤ n, the i-sections of A are the sets A_{1}, A_{2}, …, A_{k} ⊂ [k]^{n−1} defined by

A_{t} = A_{t}^{(i)} = {x ∈ [k]^{n−1} : (x_{1}, …, x_{i−1}, t, x_{i+1}, …, x_{n}) ∈ A}.

The i-compression C_{i}(A) ⊂ [k]^{n} is defined by giving its i-sections: for t = 1, 2, …, k, we take |C_{i}(A)_{t}| = |A_{t}| with C_{i}(A)_{t} an initial segment of [k]^{n−1} for all t. Note that |C_{i}(A)| = |A|.

We say that A is i-compressed if C_{i}(A) = A. (This agrees with the previous definition for n = 2.)

Theorem 11 (Isoperimetric inequality in the grid). Let A ⊂ [k]^{n} and let C be the initial segment of length |A| in the simplicial order on [k]^{n}. Then |N(A)| ≥ |N(C)|. In particular, if |A| ≥ |{x : |x| ≤ r}| then |N(A)| ≥ |{x : |x| ≤ r + 1}|.

Proof. The proof is by induction on n. The case n = 1 is easy: we have |N(A)| ≥ |A| + 1 for all A ⊂ [k]^{1} apart from A = ∅ and A = [k]. Claim. For any A ⊂ [k]^{n} and 1 ≤ i ≤ n, we have |N(C_{i}(A))| ≤ |N(A)|. Proof of claim. Write B for C_{i}(A). For any t, we have

N(A)_{t} = N(A_{t}) ∪ A_{t−1} ∪ A_{t+1}

(taking A_{0} = A_{k+1} = ∅) and so

|N(A)_{t}| = |N(A_{t}) ∪ A_{t−1} ∪ A_{t+1}|.

Similarly,

|N(B)_{t}| = |N(B_{t}) ∪ B_{t−1} ∪ B_{t+1}|.

Now, |B_{t−1}| = |A_{t−1}| and |B_{t+1}| = |A_{t+1}|, and |N(B_{t})| ≤ |N(A_{t})| by the induction hypothesis. But B_{t−1} and B_{t+1} are initial segments of the simplicial order, as is N(B_{t}). So B_{t−1}, B_{t+1} and N(B_{t}) are nested, and so |N(B)_{t}| ≤ |N(A)_{t}| for each t. Thus |N(B)| ≤ |N(A)|. // Among all B ⊂ [k]^{n} with |B| = |A| and |N(B)| ≤ |N(A)|, choose one with ∑_{x∈B} h(x) minimal, where h(x) denotes the position of x in the simplicial order. This B must be i-compressed for all i, otherwise V_{i}(B) would contradict the choice of B. But, as before, we cannot deduce immediately that B = C. Our argument now divides into two cases. Case (i): n = 2. In this case, B is i-compressed for all i if and only if it is a down-set (meaning if x ∈ B and y_{i} ≤ x_{i} for all i then y ∈ B). We want |N(B)| ≥ |N(C)|. Suppose B ≠ C. Let r = min{|x| : x ∉ B} and let s = max{|y| : y ∈ B}. Then r ≤ s. If r = s then clearly |N(B)| ≥ |N(C)| so we may assume that r < s. We cannot have {x : |x| = r} ⊂ B^{c} or {y : |y| = s} ⊂ B as B is a down-set.

So there exist x and x′ with |x| = |x′| = r, x ∉ B, x′ ∈ B and x′ = x ± (e_{1} − e_{2}) (where e_{i} = (0, …, 0, 1, 0, …, 0) with 1 in the ith position); and there exist y and y′ with |y| = |y′| = s, y ∈ B, y′ ∉ B and y′ = y ± (e_{1} − e_{2}). Let B′ = B ∪ {x} − {y}. Then |B′| = |B| and |N(B′)| ≤ |N(B)|, contradicting the choice of B, and we are done. Case (ii): n ≥ 3. If x ∈ B has x_{n} > 1 then x − e_{n} + e_{i} ∈ B for any i with x_{i} < k, as B is j-compressed for any j ≠ i, n. (Note that this is where we require dimension at least 3.) So N(B_{t}) ⊂ B_{t−1} for all t ≥ 2 (where B_{t} = B_{t}^{(n)} etc.). Thus

N(B)_{t} = N(B_{t}) ∪ B_{t+1} ∪ B_{t−1} = B_{t−1}

for all t ≥ 2. So

|N(B)| = |B_{k−1}| + |B_{k−2}| + ⋯ + |B_{1}| + |N(B_{1})|
= |B| − |B_{k}| + |N(B_{1})|.

Similarly,

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

Thus it suffices to show that:

(i) |B_{k}| ≤ |C_{k}|; and
(ii) |B_{1}| ≥ |C_{1}|.

Define D ⊂ [k]^{n} by D_{k} = B_{k} and D_{t} = N(D_{t+1}) for t = k − 1, k − 2, …, 1. Then D is an initial segment of the simplicial order and D ⊂ B, so |D| ≤ |B|, so D ⊂ C and so D_{k} ⊂ C_{k}. This establishes (i).

Next define E ⊂ [k]^{n} by E_{1} = B_{1} and E_{t} = {x ∈ [k]^{n−1} : N({x}) ⊂ E_{t−1}} for t = 2, 3, …, k. Then E is an initial segment of the simplicial order and B ⊂ E, so |E| ≥ |B| = |C|, so C ⊂ E and so E_{1} ⊃ C_{1}. This establishes (ii).

Corollary 12. Let A ⊂ [k]^{n} with |A| ≥ |{x : |x| ≤ r}|. Then for any t = 1, 2, 3, …, we have |A_{(t)}| ≥ |{x : |x| ≤ r + t}.

Proof. Induction on t.

Remark. We can check from Corollary 12 that for any fixed k, the sequence [k]^{1}, [k]^{2}, [k]^{3}, … forms a normal Lévy family.

1.4.2 Edge-isoperimetric inequalities in the grid

Given A ⊂ [k]^{n} with |A| fixed, how do we minimize |∂A|? Consider what happens in [k]^{2} as we vary |A|: for small |A|, we take roughly a square-shaped set until |A| = k^{2}/4 when a k by |A|/k column takes over; for large |A|, it is best to take the complement of a square. Unfortunately, these extremal sets are not nested.

In the 3-dimensional grid [k]^{3}, we begin with cubes [a]^{3}, then ‘square columns’ [a]^{2} × [k], then ‘half-spaces’ [a] × [k]^{2}, then complements. The situation in n dimensions is similar.

Thus compressions cannot help us. However, this result has been proven.

1.5 Other isoperimetric problems

In general, very few isoperimetric inequalities are known. For example, consider the layer X^{(r)}, with x adjacent to y if x = y ∪ {i} − {j} for some i and j (i.e. x and y are adjacent if they have distance 2 in Q_{n}). Here nothing is known. The nicest case is the middle layer r = n/2, where it is conjectured that sets of the form {y ∈ X^{(r)} : d(x, y) ≤ k} (for some fixed x) are best, for example {y ∈ X^{(r)} : |y ∩ {1, 2, …, r}| ≥ r − k}. This is unknown!

2 Intersecting families

Say A ⊂ PX is intersecting if for all x, y ∈ A we have x ∩ y ≠ ∅. How large can A be?

We could take A = {x ∈ PX : 1 ∈ x}. This has |A| = 2^{n−1}. It is impossible to beat this:

Proposition 13. Let A ⊂ PX be intersecting. Then |A| ≤ 2^{n−1}.

Proof. For each x ∈ PX, we cannot have both x, x^{c} ∈ A.

Remark. The extremal system is certainly not unique—for example, if n is odd we can take {x ∈ PX : |x| > n/2}. A better question is: how large can an intersecting A ⊂ X^{(r)} be? If r > n/2 we can take the whole of X^{(r)}. If r = n/2 we can take one of x, x^{c} for each x, giving |A| = \frac{1}{2} \binom{n}{r}. So we shall focus on r < n/2. One obvious candidate is A = \{x ∈ X^{(r)} : 1 ∈ x\}. For example, in [8]^{3} this has order \binom{7}{2} = 21, while the family \{x ∈ [8]^{3} : |x ∩ \{1, 2, 3\}| ≥ 2\} has order 1 + \binom{3}{2}\binom{5}{1} = 16 < 21.

Theorem 14 (Erdős-Ko-Rado Theorem). If A ⊂ X^{(r)} (r < n/2) is intersecting then |A| ≤ \binom{n−1}{r−1}.

Proof. The condition x ∩ y ≠ ∅ is equivalent to x ⊄ y^{c}. So writing Ā for the family {x^{c} : x ∈ A}, we have ∂^{+(n−2r)}A disjoint from Ā. Suppose |A| > \binom{n−1}{r−1}, so also |Ā| > \binom{n−1}{r−1}. We have |A| ≥ |\{x ∈ X^{(r)} : 1 ∈ X\}|, so |∂^{+}A| ≥ |{x ∈ X^{(r+1)} : 1 ∈ X}| (by the Kruskal-Katona theorem), and so, inductively, we get |∂^{+(n−2r)}A| ≥ |\{x ∈ X^{(n−r)} : 1 ∈ x\}| = \binom{n−1}{n−r−1}. Thus inside X^{(n−r)}, which has size \binom{n}{r}, we have disjoint sets of sizes at least \binom{n−1}{n−r−1} and greater than \binom{n−1}{r−1}. But \binom{n−1}{n−r−1} + \binom{n−1}{r−1} = \binom{n−1}{r} + \binom{n−1}{r−1} = \binom{n}{r}, a contradiction.

Remarks. 1. There are many other nice proofs.

2. The largest intersecting family has size \binom{n−1}{r−1} = \frac{r}{n} \binom{n}{r}; the chance that a random r-set contains 1 is \frac{r}{n}.

2.1 t-intersecting families

We say that A ⊂ PX is t-intersecting if |x ∩ y| ≥ t for all x, y ∈ A. How large can A be? For example, for t = 2 we could take {x ∈ PX : 1, 2 ∈ x} or {x ∈ PX : |x| ≥ n/2 + 1}.

Theorem 15 (Katona’s t-intersecting theorem). Let A ⊂ PX be tintersecting, with n + t even. Then |A| ≤ |X^{(≥(n+t)/2)}|.

Proof. If |x ∩ y| ≥ t then d(x, y^{c}) ≥ t, as there are at least t points which are in x but not in y^{c}. So letting Ā = {x^{c} : x ∈ A}, we have that A_{(t−1)} and Ā are disjoint.

Now, supppose |A| > |X^{(≥(n+t)/2)}| = |X^{(≤(n−t)/2)}|. Then, by Harper’s theorem, we have |A_{(t−1)}| ≥ |X^{(≤(n+t)/2−1)}|. But then |A_{(t−1)}^{c}| ≥ |X^{(≤(n+t)/2−1)}|, a contradiction.

Remark. The same proof gives that if n + t is odd then

|A| ≤ |X^{(≥(n+t+1)/2)} ∪ {x ∈ X^{((n+t−1)/2)} : n ∉ x}|.

What happens for r-sets, i.e. for A ⊂ X^{(r)}? In [8]^{(4)}, for t = 2, the family A = \{x ∈ [8]^{(4)} : 1, 2 ∈ x\} has |A| = \binom{6}{2} = 15; but the family B = \{x ∈ [8]^{(4)} : |x ∩ \{1, 2, 3, 4\}| ≥ 3|\} has |B| = 1 + \binom{4}{3}\binom{4}{1} = 17 > 15.

Write A_{α} = {x ∈ [n]^{(r)} : |x ∩ [t + 2α]| ≥ t + α} for α = 0, 1, 2, 3, . . .. The Frankl conjecture was that if A ⊂ X^{(r)} is t-intersecting then |A| ≤ max{|A_{α}| : α = 0, 1, 2, … }. This was recently proved by Ahlswede and Khachatrian.

2.2 Covering by intersecting families

How many intersecting families do we need to cover PX − {∅}? In other words, if PX − {∅} = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{s} with each A_{i} an intersecting family, how small can s be?

We clearly need at least n families (one for each singleton); and, equally clearly, n families will suffice—for example, take A_{i} = {x ∈ PX : i ∈ x}.

What happens for r-sets? How many intersecting families do we need to cover X^{(r)}?

If r > n/2 then X^{(r)} itself is intersecting. If r = n/2 then we can cover by two intersecting families: for each x, select one of x and x^{c} for A_{1} and the other for A_{2}. So we may assume that r < n/2.

We clearly need at least ⌊n/r⌋ as there exist ⌊n/r⌋ disjoint r-sets. Moreover, we need at least ⌈n/r⌉ families, as each intersecting family has at most r/n of all r-sets.

Can we achieve this? Well, we can achieve n − 2r + 2 as follows: put A_{i} = {x ∈ X^{(r)} : i ∈ x} for 1 ≤ i ≤ n−2r+1, and A_{n−2r+2} = [n−2r+2, n]^{(r)}.

Our aim is to prove Kneser’s conjecture, that we need at least n − 2r + 2 intersecting families to cover X^{(r)}. It turns out that the key tool will be the Borsuk-Ulam Theorem:

Theorem 16 (Borsuk-Ulam theorem). Let f: S^{n} → ℝ^{n} be continuous. Then there exists x ∈ S^{n} with f(x) = f(−x).

For example, in the case n = 1, suppose we have a continuous f: S^{1} → ℝ. Put g(x) = f(x) − f(−x). If g(x) > 0 then g(−x) < 0. So if g is not identically zero then there is some x with g(x) > 0 and then by the Intermediate Value Theorem there is some y with g(y) = 0.

The result for the case n = 2 is not quite intuitively obvious. Remark. The Borsuk-Ulam theorem trivially implies that there is no continuous injection from S^{n} to ℝ^{n}, and so in particular ℝ^{n+1} is not homeomorphic to ℝ^{n}—this is the “Brouwer invariance of domain theorem” and is hard to prove. (For example, why are ℝ^{3} and ℝ^{4} not homeomorphic?)

We say that f: S^{n} → ℝ^{n} is antipodal if f(−x) = −f(x) for all x.

Theorem 17. The following are equivalent:

(i) the Borsuk-Ulam theorem;

(ii) if f: S^{n} → ℝ^{n} is an antipodal map then there is some x ∈ S^{n} with f(x) = 0;

(iii) there is no continuous antipodal map f : S^{n} → S^{n−1}.

Proof. (i) ⟹ (ii). If f: S^{n} → ℝ^{n} is antipodal then, by (i), we have f(x) = f(−x) for some x, whence f(x) = 0 (as f(−x) = −f(x)). (ii) ⟹ (i). Given a continuous f: S^{n} → ℝ^{n}, define g: S^{n} → ℝ^{n} by g(x) = f(x) − f(−x). Then g is antipodal, so g(x) = 0 for some x, i.e. f(x) = f(−x). (ii) ⟹ (iii). If f: S^{n} → S^{n−1} then f(x) ≠ 0 for all x ∈ S^{n}. (iii) ⟹ (ii). Suppose f: S^{n} → ℝ^{n} is antipodal and continuous with f(x) ≠ 0 for all x ∈ S^{n}. Define g: S^{n} → S^{n−1} by g(x) = f(x)/∥f(x)∥ (where ∥x∥ = \sqrt{x_{1}^{2} + x_{2}^{2} + ⋯ + x_{n}^{2}}). Then g is continuous and antipodal, a contradiction.

Suppose A_{1}, A_{2}, …, A_{k} ⊂ S^{n} are closed sets that cover S^{n} with no A_{i} containing an antipodal pair {x, −x}. How small can k be?

It is easy to obtain k = n + 2: take A_{i} = {x ∈ S^{n} : x_{i} ≥ ε} for 1 ≤ i ≤ n + 1, and A_{n+2} = {x ∈ S^{n} : x_{i} ≤ ε for all i}. This works if ε < 1/\sqrt{n}.

Theorem 18. The following are equivalent:

(i) the Borsuk-Ulam theorem;

(ii) if A_{1}, A_{2}, …, A_{n+1} ⊂ S^{n} are closed sets covering S^{n} then some A_{i} contains an antipodal pair {x, −x}; (iii) if A_{1}, A_{2}, …, A_{n+1} ⊂ S^{n} cover S^{n} with each A_{i} open or closed then some A_{i} contains an antipodal pair.

Proof. (i) ⟹ (ii). Define f: S^{n} → ℝ^{n} by

f(x) = (d(x, A_{1}), d(x, A_{2}), …, d(x, A_{n})).

Then f is continuous so, by (i), there exists x ∈ S^{n} with d(x, A_{i}) = d(−x, A_{i}) for all i with 1 ≤ i ≤ n. If x, −x ∈ A_{n+1} then we are done. If not, we may assume without loss of generality that x ∈ A_{i} for some i with 1 ≤ i ≤ n, so d(x, A_{i}) = 0 whence d(−x, A_{i}) = 0 whence −x ∈ A_{i} (as A_{i} closed). (ii) ⟹ (i). Suppose f: S^{n} → S^{n−1} is continuous and antipodal. Let A_{1}, A_{2}, …, A_{n+1} be closed sets covering S^{n−1} with no A_{i} containing an antipodal pair. Then f^{−1}(A_{1}), f^{−1}(A_{2}), …, f^{−1}(A_{n+1}) would be closed sets covering S^{n} with none containing an antipodal pair, a contradiction. (iii) ⟹ (ii). Trivial.

(i) ⟹ (iii). As for (i) ⟹ (ii), we get x ∈ S^{n} with d(x, A_{i}) = d(−x, A_{i}) for all i with 1 ≤ i ≤ n. If x, −x ∈ A_{n+1} then we are done. If not, we may assume without loss of generality that x ∈ A_{i} for some i with 1 ≤ i ≤ n, so d(x, A_{i}) = 0 whence d(−x, A_{i}) = 0.

If A_{i} is closed then −x ∈ A_{i}.

If A_{i} is open then we have {y ∈ S^{n} : d(x, y) < ε} ⊂ A_{i} for some ε > 0. But some z with d(z, −x) < ε belongs to A_{i} (as d(−x, A_{i}) = 0).

Remark. The result of (ii) in Theorem 18 is sometimes called the Lusternik-Schnirelman theorem.

We have S^{n} = {x ∈ ℝ^{n+1} : ∥x|| = 1}. We shall often regard S^{n} instead as the set {x ∈ ℝ^{n+1} : ∑_{i=1}^{n+1} |x_{i}| = 1}. This is permissible, as the map

θ: {x ∈ ℝ^{n+1} : ∑_{i=1}^{n+1} |x_{i}| = 1} → {x ∈ ℝ^{n+1} : ∥x∥ = 1}
x ↦ \frac{x}{∥x∥}

is a homeomorphism preserving antipodality.

Write S_{+}^{n} = {x ∈ S^{n} : x_{n+1} ≥ 0} and S_{−}^{n} = {x ∈ S^{n} : x_{n+1} ≤ 0}. Regarding ℝ^{n} as a subset of ℝ^{n+1} in the obvious way, we have S_{+}^{n}∩S_{−}^{n} = S^{n−1}.

A k-simplex is ℝ^{n} is a set of the form [x_{1}, x_{2}, …, x_{k+1}], the convex hull {∑_{i=1}^{k+1} λ_{i}x_{i} : λ_{i} ≥ 0 for all i, ∑_{i=1}^{k+1} λ_{i} = 1} of points x_{1}, x_{2}, …, x_{k+1} in general position (i.e. no (k − 1)-dimensional plane contains all of them).

The faces of [x_{1}, x_{2}, …, x_{k+1}] are all simplices of the form [x_{i_{1}}, x_{i_{2}}, …, x_{i_{r}}] for any r.

A simplicial complex in ℝ^{n} is a finite set F of simplices such that

1. if σ ∈ F and τ is a face of σ then τ ∈ F; and

2. if σ, τ ∈ F and σ ∩ τ ≠ ∅ then σ ∩ τ is a face of σ.

We say that F is a simplicial decomposition of F̄ = ⋃ F.

For example, we obtain a simplicial decomposition of S^{n} by taking

F = {[±e_{i_{1}}, ±e_{i_{2}}, …, ±e_{i_{r}}] : 1 ≤ r ≤ n + 1, i_{1} < i_{2} < ⋯ < i_{r}}.

This is the standard simplicial decomposition of S^{n}, denoted by F^{n}. It is a regular simplicial decomposition of S^{n}, meaning

1. if σ ∈ F then −σ ∈ F; and

2. for all k with 0 ≤ k ≤ n − 1, f contains a simplicial decomposition of S^{k}.

Remark. It is easy to obtain other regular simplicial decompositions of S^{n}. For example, if F is a regular simplicial decomposition of S^{n} then we get another one by subdividing each simplex of F using the midpoints of its faces. This is called the barycentric subdivision of F.

Let F and F′ be simplicial complexes with V (F) and V (F′) their vertexsets (the sets of 0-simplices). A simplicial map from F to F′ is a function f: V (F) → V (F′) such that whenever {x_{1}, x_{2}, …, x_{d+1}} is the vertex-set of a simplex in F then {f(x_{1}), f(x_{2}), …, f(x_{d+1})} is the vertex-set of a simplex in F′. (Note that f(x_{1}), f(x_{2}), …, f(x_{d+1}) need not be distinct.) We can then extend f to a map from F̄ to F̄′ that maps simplices of F linearly to simplices of F′.

For example, the inclusion map ι: F^{k} → F^{n} (k ≤ n) is a simplicial map, as is the antipodal map x ↦ −x from F^{n} to F^{n}.

We observe that a map f: V (F) → V (F^{n}) is simplicial if and only if no 1-simplex [x, y] ∈ F has f(x) = e_{i} and f(y) = −e_{i} for some i.

Let f: V (F) → V (F^{n}) be a simplical map, and let σ ∈ F be a ksimplex. We shall say that σ is positive or positive alternating if we have f(x) = [e_{i_{1}}, −e_{i_{2}}, e_{i_{3}}, …, (−1)^{k}e_{i_{k+1}}]. for some i_{1} < i_{2} < ⋯ < i_{k+1}, and that σ is negative if we have f(σ) = [−e_{i_{1}}, e_{i_{2}}, −e_{i_{3}}, …, (−1)^{k+1}e_{i_{k+1}}] for some i_{1} < i_{2} < ⋯ < i_{k+1}. If σ is neither positive nor negative then we say that σ is neutral.

The ‘combinatorial heart’ of the Borsuk-Ulam theorem is:

Lemma 19. Let F be a regular simplicial decomposition of S^{k}, and let f: F → F^{n} be an antipodal simplicial map. Then f has a positive k-simplex.

Proof. Let p(f) denote the number of positive k-simplices in f. We shall show, by induction on k, that p(f) is odd.

The case k = 0 is easy, for S^{0} is two antipodal points and so exactly one maps to an e_{i}.

So suppose k > 0. Then σ is positive precisely when −σ is negative, so p(f) is the number of non-neutral k-simplices in S_{+}^{k}.

How many positive (k −1)-simplices does a k-simplex σ ⊂ S_{+}^{k} contain? If σ is non-neutral then it contains one positive (k − 1)-simplex. If σ is neutral then it contains either two or no positive (k − 1)-simplices.

How many k-simplices in S_{+}^{k} contain a fixed positive (k − 1)-simplex τ in S_{+}^{k}? If τ ⊄ S^{k−1} then two, and if τ ⊂ S^{k−1} then one. Thus, modulo 2, p(f) is the number of positive (k−1)-simplices in S^{k−1}, i.e. p(f) ≡ p(f|_{S_{k−1}}) (mod 2).

Corollary 20. Let F be a regular simplicial decomposition of S^{n+1}. Then there is no antipodal simplicial map from F to F^{n}.

Proof. No (n + 1)-simplex can be positive.

Proof (of Theorem 16). By Theorem 18, it is enough to show that if A_{1}, A_{2}, …, A_{n+1} is a closed cover of S^{n} then there is some i with A_{i} containing an antipodal pair.

So suppse that A_{1}, A_{2}, …, A_{n+1} is a closed cover of S^{n} with no A_{i} containing an antipodal pair. Then A_{1}, −A_{1}, A_{2}, −A_{2}, …, A_{n}, −A_{n} must cover S^{n}, as if they miss x then they also miss −x, whence x, −x ∈ A_{n+1}, a contradiction. Let ε = min{d(A_{1}, −A_{1}), d(A_{2}, −A_{2}), …, d(A_{n}, −A_{n})}, and let F be a regular simplicial decomposition of S^{n} in which every simplex has diameter less than ε (for example, we can take F to be an iterated barycentric subdivision of F^{n}). Given x ∈ S^{n}, set f(x) = (−1)^{r}e_{s} where (−1)^{r}A_{s} is the first of A_{1}, −A_{1}, A_{2}, −A_{2}, …, A_{n}, −A_{n} that contains x. This f: F → F^{n−1} is simplicial (as no [x, y] ∈ F has x ∈ A_{i}, y ∈ −A_{i} by choice of ε) and antipodal, a contradiction.

Theorem 21 (Kneser’s conjecture, proved by Lovász). Let r < n/2 and let A_{1}, A_{2}, …, A_{d} be a collection of intersecting families covering [n]^{(r)}. Then d ≥ n − 2r + 2.

Proof. Suppose d = n − 2r + 1. Let x_{1}, x_{2}, …, x_{n} be points in general position in S^{d} ⊂ ℝ^{d+1} (i.e. no d-dimensional subspace through the origin contains d + 1 of the x_{i}). Identify [n] with {x_{1}, x_{2}, …, x_{n}}. For x ∈ S^{d}, write H_{x} = {y ∈ S^{d} : ⟨x, y⟩ > 0}. For 1 ≤ i ≤ d, let C_{i} be the set of x ∈ S^{n} with H_{x} containing an r-set from A_{i}. Let C_{d+1} = S^{d} − (C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{d}), so that C_{d+1} is the set of x ∈ S^{d} with H_{x} containing at most r − 1 of x_{1}, x_{2},…, x_{n}. Then C_{1}, C_{2}, …, C_{d} are open and C_{d+1} is closed, so some C_{i} contains an antipodal pair {x, −x}. We cannot have 1 ≤ i ≤ d since H_{x} and H_{−x} are disjoint whence A_{i} would contain two disjoint r-sets. Thus i = d + 1, so H_{x} ∪ H_{−x} contains at most 2(r − 1) of x_{1}, x_{2}, …, x_{n}, whence {y ∈ S^{d} : ⟨x, y⟩ = 0} contains at least n − 2(r − 1) = d + 1 of x_{1}, x_{2}, …, x_{n}, a contradiction.

The Kneser graph K(n, r) (r < n/2) is the graph on vertex set [n]^{(r)} with x joined to y if x ∩ y = ∅. For example K(5, 2) is the Petersen graph. So an intersecting family in [n]^{(r)} is an independent set in K(n, r). And, for any graph G, colouring G with k colours is equivalent to partitioning G into k independent sets. So Theorem 21 can be rephrased as:

Theorem 22. χ(K(n, r)) = n − 2r + 2.

Note. The chromatic number χ is large even though there are huge independent sets (containing n/r of all vertices).

2.3 Modular intersection theorems

If A ⊂ [n]^{(r)} is intersecting, i.e. |x ∩ y| ≠ 0 for x, y ∈ A, we know that |A| ≤ \binom{n−1}{r−1}. What if, instead, we do not allow |x ∩ y| ≡ 0 modulo some number?

Say, for example, r is odd and A ⊂ [n]^{(r)} has |x ∩ y| odd for all x, y ∈ A. We can achieve |A| = \binom{⌊(n−1)/2⌋}{(r−1)/2} by taking A to consist of all sets containing 1 and (r − 1)/2 of the pairs 23, 45, … (finishing at (n − 1)n if n is odd and (n − 2)(n − 1) if n is even).

How about r odd, A ⊂ [n]^{(r)} such that |x ∩ y| is even for all x, y ∈ A with x ≠ y? We could take {x ∈ [n]^{(r)} : 1, 2, …, r − 1 ∈ x}, which has |A| = n − r + 1. Amazingly:

Theorem 23. Let r be odd, and let A ⊂ [n]^{(r)} have |x ∩ y| even for all x, y ∈ A with x ≠ y. Then |A| ≤ n.

Proof. Our main idea is to write down |A| linearly independent points in an n-dimensional vector space.

View Q_{n} as ℤ_{2}^{n} by identifying x ∈ P[n] with x̄ ∈ ℤ_{2}^{n} where

x̄_{i} = \{ \begin{matrix}1 & if i ∈ x \\ 0 & if i ∉ x \end{matrix} .

For example, if x = {1, 3, 5} then x̄ = (1, 0, 1, 0, 1, 0, 0, …); this is simply the usual identification.

For x ∈ A, we have ⟨x̄, x̄⟩ = 1 (as |x| is odd). For x, y ∈ A with x ≠ y, we have ⟨x̄, ȳ⟩ = 0 (as |x ∩ y| is even). So the set {x̄ : x ∈ A} is linearly independent over ℤ^{2}: if ∑_{x∈A} λ_{x}x̄ = 0 then, by taking the inner product with x̄, we see that λ_{x} = 0 for each x ∈ A.

What happens if r is even?

For A ⊂ [n]^{(r)} with |x ∩ y| even for all x, y ∈ A, we can get A large, for example |A| = \binom{⌊n/2⌋}{r/2}. For A ⊂ [n]^{(r)} with |x ∩ y| odd for all x, y ∈ A with x ≠ y, we must have |A| ≤ n + 1, because we may set A′ ⊂ [n + 1]^{(r+1)} to be {x ∪ {n + 1} : x ∈ A} and apply Theorem 23.

So our conclusion is that to get very small bounds on |A| for A ⊂ [n]^{(r)} we should forbid |x ∩ y| ≡ r (mod 2) for x, y ∈ A with x ≠ y. Does this generalize?

We shall now show that ‘s allowed values for |x ∩ y| modulo p implies |A| ≤ \binom{n}{s}’.

Theorem 24 (Frankl, Wilson). Let p be a prime. Let A ⊂ [n]^{(r)} be such that there are some integers λ_{1}, λ_{2}, …, λ_{s}, no λ_{i} ≡ r (mod p), for which given any x, y ∈ A with x ≠ y, we have |x ∩ y| ≡ λ_{i} (mod p) for some i. Then |A| ≤ \binom{n}{s}. In particular, if A ⊂ [n]^{(r)} satisfies |x ∩ y| ≢ r (mod p) for all distinct x, y ∈ A, then |A| ≤ \binom{n}{p−1}.

Remarks. 1. \binom{n}{s} is a polynomial independent of r.

2. In general, we cannot improve on \binom{n}{s}; for example, we can take A = [n]^{(s)} if r = s. If r > s, we can take A = {x ∈ [n]^{(r)} : 1, 2, …, r − s ∈ x}; this gives |A| = \binom{n−r+s}{s}, which is very close to \binom{n}{s} (for fixed r).

3. If we allow |x ∩ y| ≡ r (mod p) then there is no polynomial bound: taking r = a + λp (0 ≤ a < p), we can obtain |A| = \binom{⌊(n−a)/p⌋}{λ} (by taking A to consist of all sets containing the points 1, 2, …, a together with λ of the blocks [a + 1, a + p], [a + p + 1, a + 2p], …, [a + (λ − 1)p + 1, a + λp]—this grows with r.

Proof. We seek a vector space V of dimension at most \binom{n}{s} and |A| linearly independent vectors in V. We may assume without loss of generality that r > s.

For i < j, let N(i, j) be the \binom{n}{i} × \binom{n}{j} matrix, with rows indexed by [n]^{(i)} and columns indexed by [n]^{(j)}, given by

N(i, j)_{xy} = \{ \begin{matrix}1 & if x ⊂ y \\ 0 & otherwise \end{matrix} .

So N(s, r) has \binom{n}{s} rows. Let V be their linear span over ℝ. Then we have dim V ≤ \binom{n}{s}.

Consider N(i, s)N(s, r) for any 0 ≤ i ≤ s. Its rows belong to V. Also,

(N(i, s)N(s, r))_{xy} = \{ \begin{matrix}\binom{r−i}{s−i} & x ⊂ y \\ 0 & otherwise \end{matrix}

(as N(i, s)N(s, r) is simply the number of s-sets z with x ⊂ z ⊂ y). So N(i, s)N(s, r) = \binom{r−i}{s−i}N(i, r), whence N(i, r) has rows in V.

Now consider M(i) = N(i, r)^{T} N(i, r). It has rows in V. But M(i)_{xy} is the number of i-sets z with z ⊂ x and z ⊂ y, i.e. M(i)_{xy} = \binom{|x∩y|}{i}. ‘So we can get any polynomial in |x ∩ y|.’

Write the polynomial (X −λ_{1})(X −λ_{2}) ⋯ (X −λ_{s}) as ∑_{i=0}^{s} a_{i}\binom{X}{i}, where a_{0}, a_{1}, …, a_{s} ∈ ℤ; this is possible as, for each i, i!\binom{X}{i} is monic. Let M = ∑_{i=0}^{s} a_{i}M(i). All its rows are in V. Then

M_{xy} is \{ \begin{matrix}0 (mod p) & when |x ∩ y| ≡ λ_{i} (mod p) for some i = 1, 2, …, s \\ ≢ 0 (mod p) & otherwise \end{matrix} .

Consider the submatrix whose rows and columns are indexed by A. This submatrix has |A| rows, which are linearly independent over ℤ_{p} and so are certainly linearly independent over ℝ. Hence we have |A| linearly independent rows of M and so |A| ≤ \binom{n}{s}.

Remark. The theorem fails if p is not prime. Grolmusz constructed, for each n, a value r ≡ 0 (mod 6) and a set system |A| ⊂ [n]^{(r)} such that for any distinct x, y ∈ A, we have |x ∩ y| ≢ 0 (mod 6), but with |A| ≥ n^{c log n/ log log n} (for some c). There is a similar construction for any non-prime modulus.

If we have some half-size sets, we expect the intersections to have size around n/4, but they are very unlikely to have size exactly n/4. Nevertheless:

Corollary 25. Let p be prime and let A ⊂ [4p]^{(2p)} with |x ∩ y| ≠ p for any distinct x, y ∈ A. Then |A| ≤ 2\binom{4p}{p−1}.

Remark. Note that this bound is very small: \binom{n}{n/4} ≤ 4e^{−n/32} · 2^{n} (whereas \binom{n}{n/2} ∼ (c/\sqrt{n}) · 2^{n}).

Proof. By halving the size of A if necessary, we may assume that there is no pair {x, x^{c}} ⊂ A. Then if x, y ∈ A with x ≠ y we have |x ∩ y| ≠ 0, p, so |x ∩ y| ≢ 0 (mod p), and so |A| ≤ \binom{4p}{p−1}.

2.4 Borsuk’s Conjecture

Suppose we have S ⊂ ℝ^{n} of diameter d. How many pieces do we need to break S into so that each piece has diameter strictly less than d?

For example, in ℝ^{2}, taking the vertices of an equilateral triangle shows that we need at least 3 pieces. Similarly, in ℝ^{n}, a regular n-simplex shows that we need at least n + 1 pieces.

Borsuk conjectured that n + 1 pieces suffice.

Borsuk’s conjecture is true for n = 1, 2, 3, and for S smooth, and for S symmetric. However, it is massively false.

Theorem 26 (Kahn, Kalai). For any n, there is a set S ⊂ ℝ^{n} such that to partition S into pieces of smaller diameter requires at least c^{\sqrt{n}} pieces (for some constant c > 1).

Notes. 1. Our proof will show that Borsuk’s conjecture is false for n around 2000.

2. We shall prove Theorem 26 for n of the form \binom{4p}{2} for p prime. We are then done as, for example, for all n there is a prime p with n/2 ≤ p ≤ n.

Proof. We shall construct S ⊂ Q_{n} ⊂ ℝ^{n} with S ⊂ [n]^{(r)} for some r.

For x, y ∈ [n]^{(r)}, we have d(x, y)^{2} = 2(r − |x ∩ y|). So d(x, y) increases as |x ∩ y| decreases. So we seek S ⊂ [n]^{(r)}, say with minimum intersection size k, but such that any subset of S with minimum intersection size greater than k is much smaller than S.

Identify [n] with [4p]^{(2)}—the edges of K_{4p}, the complete graph on [4p]. For each x ∈ [4p]^{(2p)}, let G_{x} be the complete bipartite graph on vertex-classes x, x^{c}. Let S = \{G_{x} : x ∈ [4p]^{(2p)}\} ⊂ [n]^{(4p^{2})}. Then |S| = \frac{1}{2} \binom{4p}{2p}.

Now, |G_{x} ∩ G_{y}| = k^{2} + (2p − k)^{2}, where k = |x ∩ y|, which is minimized at k = p. Thus if we have a piece of S, say {G_{x} : x ∈ A}, of diameter smaller than the diameter of S, then we cannot have |x ∩ y| = p for any x, y ∈ A. So |A| ≤ \binom{4p}{2p−1} by Corollary 25. Thus the number of pieces needed is at least

\begin{matrix}\frac{1}{2} & \binom{4p}{2p} \\ ( & {4p \atop p−1} & ) \end{matrix} ≥ \frac{c · 2^{4p}/\sqrt{p}}{4 · e^{−p/8} · 2^{4p}} (for some constant c)
≥ c^{′p} (for some constant c′ > 1)
≥ c^{′′\sqrt{n}} (for some constant c′′ > 1).

3 Projections

Let A ⊂ PX and let Y ⊂ X. The projection or trace of A on Y is A|Y = {x ∩ Y : x ∈ A}; thus A|Y ⊂ PY —‘project A onto the coordinates corresponding to Y ’.

Say A covers or shatters Y if A|Y = PY. The trace number of A is tr A = max{|Y | : Y shattered by A}.

Given |A|, how small can tr A be? Equivalently, how large can |A| be given tr A < k?

We could take A = X^{(<k)}. This clearly does not shatter any k-set (as if |Y | = k then Y ∉ A|Y). Our aim is to show that we cannot do better than |X^{(<k)}|.

The main idea is that this is trivial if A is a down-set (i.e. if whenever x ∈ A and y ⊂ x then also y ∈ A), since a down-set A with tr A < k must have A ⊂ X^{(<k)}.

For A ⊂ PX and 1 ≤ i ≤ n, the i-down-compression of A is the setsystem D_{i}(A) ⊂ PX defined by

D_{i}(A)_{+} = A_{+} ∩ A_{−},
D_{i}(A)_{−} = A_{+} ∪ A_{−},

i.e. we “compress A downwards in direction i”. Note that |D_{i}(A)| = |A|. We say that A is i-down-compressed if D_{i}(A) = A.

Remark. D_{i} is a 1-dimensional compression.

Theorem 27 (Sauer-Shelah Lemma). If A ⊂ PX with |A| ≥ |X^{(<k)}| + 1 then tr A ≥ k.

Proof. Claim. For any A ⊂ PX and 1 ≤ i ≤ n, we have tr D_{i}(A) ≤ tr A. Proof of claim. Write A′ for D_{i}(A). Suppose A′ shatters y; we shall show that A also shatters y.

If i ∉ Y then A′|Y = A|Y, and so we are done.

So suppose i ∈ Y. Then for z ⊂ Y with i ∉ z we have z ∪ {i} ∈ A′|Y, so there exists z ∈ A′ with x ∩ Y = z ∪ {i}. But then i ∈ x, so x, x − {i} ∈ A (by definition of A′). Thus z ∪ {i}, z ∈ A|Y. Hence A|Y = PY. // Set B = D_{n}(D_{n−1}(D_{n−2}(… (D_{1}(A)) …))). Then |B| = |A|, tr B ≤ tr A, and B is a down-set. But |B| > |X^{(<k)}|, so B contains some k-set, whence tr B ≥ k.

In general, if we have upper bounds on some projections |A|Y_{i}|, do we get upper bounds on |A|? For example, the Sauer-Shelah lemma says that if |A|Y | ≤ 2^{k} − 1 for all k-sets Y, then |A| ≤ |X^{(<k)}|.

A brick or box in ℝ^{n} is a set of the form [a_{1}, b_{1}] × [a_{2}, b_{2}] × ⋯ × [a_{n}, b_{n}] where a_{i} ≤ b_{i} for all i. A body S ⊂ ℝ^{n} is a finite union of bricks. The volume of S is written |S| or m(S). Remarks. 1. In fact, everything will go through for a general compact S ⊂ ℝ^{n}.

2. A set system A ⊂ Q_{n} gives a body

S = ⋃_{x∈A}[x_{1}, x_{1} + 1] × [x_{2}, x_{2} + 1] × ⋯ × [x_{n}, x_{n} + 1]

with |A| = m(S).

For a body S ⊂ ℝ^{n} and Y ⊂ [n], the projection of S onto the span of {e_{i} : i ∈ Y } is denoted by S_{Y}. For example, if S ⊂ ℝ^{3} then S_{1} is the projection of S onto the x-axis:

S_{1} = {x_{1} ∈ ℝ : (x_{1}, x_{2}, x_{3}) ∈ S for some x_{2}, x_{3} ∈ ℝ};

and S_{12} is the projection of S onto the xy-plane:

S_{12} = {(x_{1}, x_{2}) ∈ ℝ^{2} : (x_{1}, x_{2}, x_{3}) ∈ S for some x_{3} ∈ ℝ}.

We have that S_{A} ⊂ ℝ^{|A|}.

What bounds on |S| do we get given bounds on some S_{Y}?

For example, let S be a body in ℝ^{3}. Then trivially |S| ≤ |S_{1}||S_{2}||S_{3}| as S ⊂ S_{1} × S_{2} × S_{3}. Similarly, |S| ≤ |S_{12}||S_{3}| as S ⊂ S_{12} × S_{3}.

What if |S_{12}| and |S_{13}| are known? This tells us nothing—for example, consider S = [0, 1/n] × [0, n] × [0, n].

What if |S_{12}|, |S_{13}| and |S_{23}| are known?

Proposition 28. Let S be a body in ℝ^{3}. Then |S|^{2} ≤ |S_{12}||S_{13}||S_{23}|.

Remark. We have equality if S is a brick.

For S ⊂ ℝ^{n}, the n-sections are the sets S(x) ⊂ ℝ^{n−1} for each x ∈ ℝ defined by

S(X) = {(x_{1}, x_{2}, …, x_{n−1}) ∈ ℝ^{n−1} : (x_{1}, x_{2}, …, x_{n−1}, x) ∈ S}.

Proof (of Proposition 28). Consider first the case when each 3-section is a square, i.e. when S(x) = [0, f(x)] × [0, f(x)]. Then |S_{12}| = M^{2}, where M = max_{x∈ℝ} f(x). Also, |S_{13}| = |S_{23}| = ∫ f(x) dx, and |S| = ∫ f(x)^{2} dx. Thus we want:

(∫ f(x)^{2} dx)^{2} ≤ M^{2} (∫ f(x) dx)^{2} .

But ∫ f(x)^{2} dx ≤ M ∫ f(x) dx as f(x) ≤ M for all x, so this indeed holds. For the general case, define a body T ⊂ ℝ^{3} by

T (x) = [0, \sqrt{|S(x)|}] × [0, \sqrt{|S(x)|}].

Then |T | = |S| and |T_{12}| ≤ |S_{12}| (as |T_{12}| = max_{x∈ℝ} |T (x)|).

Let f(x) = |S(x)_{1}| and g(x) = |S(x)_{2}|. Then

|T_{23}| = |T_{13}| = ∫ \sqrt{|S(x)|} dx ≤ ∫ \sqrt{f(x)g(x)} dx.

Also, |S_{13}| = ∫ f(x) dx and |S_{23}| = ∫ g(x) dx. So we need

(∫ \sqrt{f(x)g(x)} dx)^{2} ≤ (∫ f(x) dx) (∫ g(x) dx) ,

i.e.

∫ \sqrt{f(x)}\sqrt{g(x)} dx ≤ (∫ f(x) dx)^{1/2} (∫ g(x) dx)^{1/2} ,

which is just the Cauchy-Schwarz inequality.

We say that sets Y_{1}, Y_{2}, …, Y_{r} cover [n] if ⋃_{j=1}^{r} Y_{j} = [n]. They are a k-uniform cover if each i ∈ [n] belongs to exactly k of the Y_{j}. For example, for n = 3: {1}, {2}, {3} is a 1-uniform cover, as is {1}, {2, 3}; {1, 2}, {1, 3}, {2, 3} is a 2-uniform cover; {1, 2}, {1, 3} is not uniform.

Our aim is to show that if Y_{1}, Y_{2}, …, Y_{r} form a k-uniform cover then |S|^{k} ≤ |S_{Y_{1}}||S_{Y_{2}}| ⋯ |S_{Y_{r}}|.

Let C = {Y_{1}, Y_{2}, …, Y_{r}} be a k-uniform cover of [r]. Note that C is a multiset, i.e. repetitions are allowed—for example, {12, 12, 3, 3} is a 2-uniform cover of [3]. Put C_{−} = {Y_{i} : n ∉ Y_{i}} and C_{+} = {Y_{i} − n : n ∈ Y_{i}} (as usual), so C_{−} ∪ C_{+} is a k-uniform cover of [n − 1].

Note that if n ∈ Y then |S_{Y} | = ∫ |S(x)_{Y −n}|dx (e.g. if S ⊂ ℝ^{3} then |S_{13}| = ∫ |S(x)_{1}|dx), and this holds even if Y = [n]. Also, if n ∉ Y then |S(x)_{Y} | ≤ |S_{Y} | for all x (e.g. |S_{12}| ≥ |S(x)_{12}| for all x).

In the proof of Proposition 28 we used the Cauchy-Schwarz inequality:

∫ fg ≤ (∫ f^{2})^{1/2} (∫ g^{2})^{1/2} .

Here, we’ll need Hölder’s inequality:

∫ fg ≤ (∫ |f|^{p})^{1/p} (∫ |g|^{q})^{1/q}

for (1/p) + (1/q) = 1, whence, iterating, we get

∫ f_{1}f_{2} ⋯ f_{k} ≤ (∫ |f_{1}|^{k})^{1/k} (∫ |f_{2}|^{k})^{1/k} ⋯ (∫ |f_{1}|^{k})^{1/k} .

Theorem 29 (Uniform covers theorem). Let S be a body in ℝ^{n}, and let C be a k-uniform cover of [n]. Then

|S|^{k} ≤ ∏_{Y ∈C} |S_{Y} |.

Proof. The proof is by induction on n; the case n = 1 is trivial.

Given a body S ⊂ ℝ^{n} for n ≥ 2, we have

|S| = ∫ |S(x)| dx
≤ ∫ ∏_{Y ∈C_{+}} |S(x)_{Y} |^{1/k} ∏_{Y ∈C_{−}} |S(x)_{Y} |^{1/k} dx

≤ ∏_{Y ∈C_{−}} |S_{Y} |^{1/k} ∫ ∏_{Y ∈C_{+}} |S(x)_{Y} |^{1/k} dx

≤ ∏_{Y ∈C_{−}} |S_{Y} |^{1/k} ∏_{Y ∈C_{+}} (∫ |S(x)_{Y} | dx)^{1/k}
= ∏_{Y ∈C_{−}} |S_{Y} |^{1/k} ∏_{Y ∈C_{+}} |S_{Y ∪n}|^{1/k}
= ∏_{Y ∈C} |S_{Y} |^{1/k}.

Corollary 30 (Loomis-Whitney theorem). Let S be a body in ℝ^{n}. Then

|S|^{n−1} ≤ ∏_{i=1}^{n} |S_{[n]−i}|.

Proof. The family [n] − 1, [n] − 2, …, [n] − n is an (n − 1)-uniform cover of [n].

Remark. The case n = 3 of the Loomis-Whitney theorem is Proposition 28.

Corollary 31. Let A ⊂ Q_{n}, and let C be a k-uniform cover of [n]. Then

|A|^{k} ≤ ∏_{Y ∈C} |A|Y |.

In particular, if C is a uniform cover with |A|Y | ≤ 2^{c|Y |} for all y ∈ C then |A| ≤ 2^{cn}.

Proof. For the first part, consider the body

S = ⋃_{x∈A}[x_{1}, x_{1} + 1] × [x_{2}, x_{2} + 1] × ⋯ × [x_{n}, x_{n} + 1].

Then m(S) = |A| and m(S|Y) = |A|Y | for all Y.

For the second part, suppose that C is a k-cover. Then

|A|^{k} ≤ ∏_{Y ∈C} |A|Y | ≤ ∏_{Y ∈C} 2^{c|Y |} = 2^{c ∑_{Y ∈C} |Y |} = 2^{ckn}.

Our next aim is to prove the ‘Bollobás-Thomason box theorem’, that for any body S there is a box B with |B| = |S| and |B_{Y} | ≤ |S_{Y} | for all Y. This theorem has no right to be true. For example, we can then read off all possible projection theorems—just check them for boxes.

A uniform cover C of [n] is irreducible if we cannot write C = C′ ∪ C′′ where C′ and C′′ are uniform covers. For example, if n = 3 then 12, 13, 23 form an irreducible cover but 1, 2, 3, 12, 13, 23 do not.

Lemma 32. There are only finitely many irreducible uniform covers of [n].

Proof. Suppose C_{1}, C_{2}, C_{3}, …, are distinct irreducible covers. List P[n] as E_{1}, E_{2}, …, E_{2^{n}}. Choose a subsequence C_{i_{1}}, C_{i_{2}}, C_{i_{3}} on which the number of copies of E_{1} is increasing (not necessarily strictly). Repeating for E_{2}, then E_{3}, then …, then E_{2^{n}}, we obtain a subsequence C_{j_{1}}, C_{j_{2}}, C_{j_{3}}, …, on which the number of copies of E_{i} is increasing for all i. But then C_{j_{2}} is not irreducible (as C_{j_{2}} ⊃ C_{j_{1}}), a contradiction.

Theorem 33 (Bollobás-Thomason box theorem). Let S be a (nonempty) body in ℝ^{n}. Then there is a box B ∈ ℝ^{n} with |B| = |S| and |B_{Y} | ≤ |S_{Y} | for all Y ⊂ [n].

Proof. We may assume without loss of generality that |S| > 0 and n ≥ 2. Take real variables x_{Y} for each Y ∈ P[n] with Y ≠ ∅, [n], with constraints:

(i) 0 ≤ x_{Y} ≤ |S_{Y} | for all Y;
(ii) x_{Y} ≤ ∏_{i∈Y} x_{i} for all Y with |Y | ≥ 2; and

(iii) |S|^{k} ≤ ∏_{Y ∈C} x_{Y} for each k-uniform irreducible cover C ≠ {[n]}.

Note that if (iii) is satisfied for all irreducible covers, then it is satisfied for all uniform covers. We denote the condition (iii) for all uniform covers by (iii)′. We ‘want a minimal solution’.

We have a solution, namely x_{Y} = |S_{Y} | for all Y. The solution set is compact, so there exists a solution with minimal ∑_{Y} x_{Y}. We must have x_{Y} > 0 for all Y, because every Y occurs in some uniform cover, whence (iii)′ gives |x_{Y} | > 0 (as |S| > 0). Claim. For 1 ≤ i ≤ n, x_{i} appears on the RHS of an inequality from (iii) in which equality holds. Proof of claim. We must have x_{i} on the RHS of some constraint for which equality holds, as otherwise we could decrease x_{i} (as the set of constraints is finite). It is not an inequality from (i) as (x_{i} > 0). If it is an inequality from (iii) then we are done. If it is an inequality from (ii), then x_{Y} = ∏_{j∈Y} x_{j} for some Y with {i} ∈ Y. We must have x_{Y} on the RHS of an inequality that is an equality (by minimality of x_{Y}), which must be of type (iii). So |S|^{k} = ∏_{Z∈C} x_{Z}, for some irreducible cover C with Y ∈ C. Then C − {Y } ∪ {{j} : j ∈ Y } is also a uniform cover with equality in (iii)′, and {i} belongs to this cover. Now take any irreducible cover C′ from this cover which includes {i}. // Thus for each i, we have a uniform cover C_{i} with equality in (iii) and with {i} ∈ C_{i}. Consider C = ⋃_{i=1}^{n} C_{i}. Then C is a uniform cover with equality in (iii)′, and {1}, {2}, …, {n} ∈ C. Put C′ = C − {{1}, {2}, …, {n}}. Then C′ is also a uniform cover, say a k-cover, and we have |S|^{k} ≤ ∏_{Y ∈C′} x_{Y} and |S|^{k+1} = ∏_{Y ∈C′} x_{Y} ∏_{i=1}^{n} x_{i}. Thus |S| = ∏_{i=1}^{n} x_{i}. Now for any Y, consider the uniform cover {Y, Y^{c}} of [n]. We have

|S| ≤ x_{Y} x_{Y^{c}} ≤ ( ∏_{i∈Y} x_{i})( ∏_{i∈Y^{c}} x_{i}) = |S|,

so x_{Y} = ∏_{i∈Y} x_{i}. Thus B = [0, x_{1}] × [0, x_{2}] × ⋯ × [0, x_{n}] will do.

3.1 Intersecting families of graphs

What happens to intersecting families if we have more structure in our ground set?

One natural example is to take our ground set to be [n]^{(2)}, the edges of the complete graph on [n]. There are a total of 2^{\binom{n}{2}} graphs on [n].

How many graphs can we find such that any two intersect in something containing P_{2}, the path of length 2? We want to find max |A| subject to G, H ∈ A ⟹ G ∩ H ⊃ P_{2}. Clearly |A| ≤ (1/2)2^{\binom{n}{2}} (as we cannot have both G ∈ A and G^{c} ∈ A for any graph G). We can get |A| ∼ (1/2)2^{\binom{n}{2}} by fixing x ∈ [n] and taking

A = \{G : d_{G}(x) ≥ \frac{n}{2} + 1\};

this has

|A| ∼ (\frac{1}{2} − \frac{c}{\sqrt{n}}) 2^{\binom{n}{2}}.

Similarly, we can get |A| ∼ (1/2)2^{\binom{n}{2}} for G ∩ H containing a star.

Conjecture 34. If G, H ∈ A ⟹ G ∩ H contains a triangle, then |A| ≤ (1/8)2^{\binom{n}{2}}.

Note that we can obtain |A| = (1/8)2^{\binom{n}{2}} by taking A to consist of all graphs G which contain some fixed triangle.

Theorem 35. Let A ⊂ P ([n]^{(2)}) be such that if G, H ∈ A then G ∩ H contains a triangle. Then |A| ≤ (1/4)2^{\binom{n}{2}}

Proof. We want |A| ≤ 2^{\binom{n}{2}−2} = 2^{\binom{n}{2}}^{(1−2/\binom{n}{2})}, so it is enough to find a uniform cover C of [n]^{(2)} such that for all Y ∈ C we have |A ∩ Y | ≤ 2^{c|Y |}, where c = 1 − 4/(n(n − 1)).

For n even, take all Y of the form B^{(2)} ∪ (B^{c})^{(2)} with |B| = |A|/2. This is clearly a uniform cover. Now for any such Y, G ∩ H is not bipartite and so G and H meet on Y. Thus A|Y is intersecting, whence

|A|Y | ≤ (1/2)2^{|Y |} = 2^{2\binom{n/2}{2}−1} = 2^{2\binom{n/2}{2}(1−1/(2\binom{n/2}{2}))},

so we need

1 − \frac{1}{2\binom{n/2}{2}} ≤ 1 − \frac{4}{n(n − 1)}.

For n odd, we do the same thing but with |B| = (n − 1)/2.

Typeset in L^{A}TEX 2ε by Paul A. Russell.