Topics in Combinatorics

W.T. Gowers, F.R.S.

Lent 2004

1 Random walks on graphs

We shall consider a graph G with n vertices that is regular of degree d. (We shall allow loops and multiple edges.) We can define a random walk on G by starting at a vertex x = x_{0}, and at each step moving from the current vertex x_{n} to one of its neighbours—each chosen with probability \frac{1}{d}.

The adjacency matrix A of G is defined by

A_{xy} = \{ \begin{matrix}1 & xy is an edge of G \\ 0 & otherwise \end{matrix}

(or more generally A_{xy} is defined to be the number of edges from x to y).

The transition matrix T is \frac{1}{d}A. Observe that T_{xy} is the probability that you go to y if you are at x.

The useful thing about T is that (T^{k})_{xy} is the probability that, after k steps, you are at y if you start at x. (Easy inductive proof.)

T is a symmetric matrix, so there is an orthonormal basis of eigenvectors v_{0}, v_{1}, …, v_{n−1} with eigenvalues λ_{0} ≥ λ_{1} ≥ ⋯ ≥ λ_{n−1}.

Lemma 1. With T defined as above, λ_{0} = 1, and λ_{1} < 1 if G is connected. Furthermore, λ_{n−1} ≥ −1, with equality iff G is bipartite.

Proof. Let ϕ : V (G) → ℝ be the constant function taking the value 1 everywhere. Then

T ϕ(x) = ∑_{y∈V (G)} T_{xy}ϕ(y) = \frac{1}{d} ∑_{y∈N(x)} ϕ(y) = 1 = ϕ(x)

(as G is d-regular). So ϕ is an eigenvector with eigenvalue 1.

Now we show that |λ_{i}| ≤ 1 for every i. Write ∥f∥_{1} for ∑_{x} |f(x)|. Then, for any ϕ : V (G) → ℝ,

∥T ϕ∥_{1} = ∑_{x∈V (G)} |\frac{1}{d} ∑_{y∈N(x)} ϕ(y)|

≤ \frac{1}{d} ∑_{x∈V (G)} ∑_{y∈N(x)} |ϕ(y)|

= \frac{1}{d} ∑_{y∈V (G)} |ϕ(y)| ∑_{x∈N(y)} 1
= ∑_{y∈V (G)} |ϕ(y)|
= ∥ϕ∥_{1}.

Hence if T ϕ = λϕ then |λ| ≤ 1.

Now, let us suppose that ∥T ϕ∥_{1} = ∥ϕ∥_{1}, so that equality holds in the inequality above. Then | ∑_{y∈N(x)} ϕ(y)| = ∑_{y∈N(x)} |ϕ(y)| for every x, so no x has neighbours y and z with ϕ(y) > 0 and ϕ(z) < 0.

Suppose that ϕ is an eigenvector and ϕ(x) = 0. Then

T ϕ(x) = \frac{1}{d} ∑_{y∈N(x)} ϕ(y) = 0,

so ϕ(y) = 0 for all y ∈ N(x). If G is connected then ϕ vanishes everywhere, a contradiction. So if ϕ is an eigenvector with eigenvalue ±1 then ϕ(x) is never 0. If the eigenvalue is 1 then the sign of ϕ(y) is the same as that of ϕ(x) for all y ∈ N(x). Hence ϕ has constant sign, so ⟨ϕ, 1⟩ = ∑_{x} ϕ(x).1 ≠ 0. So if ϕ is one of the v_{i} then ϕ = v_{0}.

If the eigenvalue is −1, then ϕ(y) has opposite sign to ϕ(x) for every y ∈ N(x). So sign ϕ defines a bipartition of G.

Lemma 2. Let G be a graph with n vertices, regular of degree d. Suppose that λ = max{|λ_{1}|, |λ_{n−1}|} < 1. Then the random walk on G converges to the uniform distribution.

Proof. Let v_{0}, v_{1}, …, v_{n} be an orthonormal basis of eigenvectors of the transition matrix T (ordered as before). Then we can write the initial distribution p_{0} of the random walk as μ_{0}v_{0} + μ_{1}v_{1} + ⋯ + μ_{n−1}v_{n−1} for some scalars μ_{0}, μ_{1}, …, μ_{n−1}.

We know that μ_{0}v_{0} is the uniform distribution by looking at the expression ∑_{x} ∑_{i=0}^{n−1} μ_{i}v_{i}(x) = ∑_{x} p_{0}(x) = 1. But ⟨v_{i}, v_{0}⟩ = 0 for all i > 0, i.e. ∑_{x} v_{i}(x) = 0 for all i > 0, so this is also ∑_{x} μ_{0}v_{0}(x), so μ_{0}v_{0} is a constant function summing to 1.

The distribution p_{k} after k steps is then

T^{k}p_{0} = μ_{0}v_{0} + μ_{1}λ_{1}^{k}v_{1} + ⋯ + μ_{n−1}λ_{n−1}^{k}v_{n−1}.

So

∥T^{k}p_{0} − μ_{0}v_{0}∥_{2}^{2} = ∑_{i=1}^{n−1} μ_{i}^{2}λ_{i}^{2k} ≤ λ^{2k} ∑_{i=1}^{n−1} μ_{i}^{2} ≤ λ^{2k}

since ∑_{i=0}^{n−1} μ_{i}^{2} = ∥p_{0}∥_{2}^{2} ≤ 1. Hence ∥T^{k}p_{0} − μ_{0}v_{0}∥_{1} ≤ λ^{k}\sqrt{n}.

But λ^{k} → 0, so p_{k} converges to the uniform distribution in ℓ_{1} (or in ℓ_{2} or in any other norm).

Definition. The total variation distance between two probability distributions μ_{1} and μ_{2} on a set X (which we will take to be finite) is given by max_{A⊂X}{|μ_{1}(A) − μ_{2}(A)|}. It is easy to see that the best A to choose is either {x : μ_{1}({x}) ≥ μ_{2}({x})} or {x : μ_{1}({x}) < μ_{2}({x})}. But since ∑ μ_{1}({x}) = ∑ μ_{2}({x}), these give the same answer, so both must give \frac{1}{2}∥μ_{1} − μ_{2}∥_{1}.

Example. The discrete cube Q_{n} has vertex set ℙ[n], where [n] = {1, 2, …, n}. Two sets A, B ⊂ [n] are joined by an edge if |AΔB| = 1, i.e. if A and B differ by exactly one element. Equivalently, it is the set of 01-sequences of length n, with (ε_{1}, ε_{2}, …, ε_{n}) joined to (ε′_{1}, ε′_{2}, …, ε′_{n}) iff ε_{i} = ε′_{i} for all but one value of i.

We shall write down a complete system of eigenvectors. Definition. Let B ⊂ [n]. The Walsh function W_{B} : ℙ[n] → ℝ is defined by W_{B}(A) = (−1)^{|A∩B|}, e.g. W_{∅}(A) = 1 for every A ⊂ [n] and W_{[n]}(A) = (−1)^{|A|}.

Claim 1. If B ≠ B′ then ⟨W_{B}, W_{B′}⟩ = 0.

Proof. For i ∈ BΔB′, we have

∑_{A⊂[n]} W_{B}(A)W_{B′}(A) = ∑_{A⊂[n]−{i}} (W_{B}(A)W_{B′}(A)+W_{B} (A ∪ {i}) W_{B} (A ∪ {i}) ).

If i ∈ B − B′ then W_{B}(A) = −W_{B} (A ∪ {i}) and W_{B′}(A) = W_{B′} (A ∪ {i}), so the big bracket is zero for every A. Similarly if i ∈ B′ − B.

Claim 2. Each W_{B} is an eigenvector of T with eigenvalue 1 − \frac{2|B|}{n}.

Proof. We have

T W_{B}(A) = \frac{1}{n} ∑_{\begin{matrix}C⊂[n] \\ |AΔC|=1 \end{matrix}} W_{B}(C)

= \frac{1}{n} ∑_{i=1}^{n} W_{B} (AΔ\{i\})
= \frac{1}{n} ∑_{i∈B} W_{B} (AΔ\{i\}) + \frac{1}{n} ∑_{i∉B} W_{B} (AΔ\{i\})

= \frac{1}{n}W_{B}(A)( − |B| + n − |B|)
= (1 − \frac{2|B|}{n}) W_{B}(A).

This proves that λ_{1} = 1 − \frac{2}{n} and λ_{n−1} = −1. We can deal with the fact that the graph is bipartite by staying still with probability \frac{1}{2}. Then the transition matrix T changes to \frac{1}{2}(T + I), so then the eigenvalue λ changes to \frac{λ+1}{2}.

We can do better as follows. If we start at a single vertex—wlog ∅—then the initial distribution is δ_{∅}. Since ∥W_{B}∥_{2} = 2^{\frac{n}{2}} , we have

δ_{∅} = 2^{−n} ∑_{B⊂[n]}⟨δ_{∅}, W_{B}⟩W_{B} = 2^{−n} ∑_{B⊂[n]} W_{B}.

If we use the transition matrix T = \frac{1}{2}(I + \frac{1}{n}A) then W_{B} has eigenvalue

1 − \frac{|B|}{n}. Then T^{k}δ_{∅} = 2^{−n} ∑_{B⊂[n]} (1 − \frac{|B|}{n}) W_{B}. So

∥T^{k}δ_{∅} − 2^{−n}W_{∅}∥_{2}^{2} = 2^{−2n} ∑_{\begin{matrix}B⊂[n] \\ B≠∅ \end{matrix}} (1 − \frac{|B|}{n})^{2k} ∥W_{B}∥_{2}^{2}

= 2^{−n} ∑_{r=1}^{n} (1 − \frac{r}{n})^{2k} \binom{n}{r}

≤ 2^{−n} ∑_{r=1}^{n} e^{\frac{−2kr}{n}} n^{r}

= 2^{−n} ∑_{r=1}^{n} (e^{log n− \frac{2k}{n}} )^{r} .

If k = Cn log n with C ≥ 1 then this is at most 2^{−n} ∑_{r=1}^{n} e^{−Cr log n} ≤ 2^{−n}2n^{−c}, so ∥T^{k}δ_{∅} −2^{−n}W_{∅}∥_{2} ≤ 2^{\frac{1}{2}} 2^{− \frac{n}{2}} n^{− \frac{C}{2}} , and so ∥T^{k}δ_{∅} −2^{−n}W_{∅}∥_{1} ≤ 2^{\frac{1}{2}} n^{− \frac{C}{2}} . Hence the mixing time is ≲ n log n (in fact ≈).

Example. For convenience, let N be odd and consider the graph on ℤ_{N}, the integers modulo N, with x joined to x ± 1. Let ω = e^{\frac{2πi}{N}} and for each r let f_{r}(x) = ω^{rx}. Then

(T f_{r})(x) = \frac{1}{2}f_{r}(x + 1) + \frac{1}{2}f_{r}(x − 1)
= \frac{1}{2}(ω^{r(x+1)} + ω^{r(x−1)})
= \frac{1}{2}(ω^{r} + ω^{−r})ω^{rx} = cos \frac{2πr}{N}.f_{r}(x).

So f_{r} is an eigenvector with eigenvalue cos \frac{2πr}{N}. So is f_{−r}, since cos is even. It follows that x ↦ cos \frac{2πrx}{N} and x ↦ sin \frac{2πrx}{N} are eigenvectors with eigenvalue cos \frac{2πr}{N}. So λ_{1} = cos \frac{2π}{N} and λ_{N−1} = cos 2π \frac{(N+1)/2}{N} = cos (π + \frac{π}{N} ) so the spectral gap is ∼ N^{−2}. So the mixing time is ≲ N^{2} log N.

Lemma 3. Let G be a d-regular graph. Then

λ_{1} = sup \{\frac{⟨T f, f⟩}{n var f} : f ≢ 0, ∑_{x} f(x) = 0\} .

Proof. Let v_{0}, v_{1}, …, v_{n−1} be an orthonormal basis of eigenvectors with eigenvalues λ_{0} ≥ λ_{1} ≥ ⋯ ≥ λ_{n−1}. Then, as ∑_{x∈V (G)} f(x) = 0, we can expand f as f = μ_{1}v_{1} + ⋯ + μ_{n−1}v_{n−1}. Then ⟨f, T f⟩ = ∑_{i=1}^{n−1} λ_{i}μ_{i}^{2} and n var f = ∑_{i=1}^{n−1} μ_{i}^{2} (= ∥f∥_{2}^{2}). But ∑_{i=1}^{n−1} λ_{i}μ_{i}^{2} ≤ λ_{1} ∑_{i=1}^{n−1} μ_{i}^{2} with equality if μ_{1} = 1 and the other μ_{i} are zero.

Now

⟨f, T f⟩ = ∑_{x} f(x)T f(x)
= \frac{1}{d} ∑_{x} f(x) ∑_{y∈N(x)} f(y)

= \frac{1}{d} ∑_{\begin{matrix}(x,y) \\ x∼y \end{matrix}} f(x)f(y)

= \frac{1}{2d} ∑_{\begin{matrix}(x,y) \\ x∼y \end{matrix}} (f(x)^{2} + f(y)^{2} − (f(x) − f(y))^{2})

= n var f − \frac{1}{2d} ∑_{\begin{matrix}(x,y) \\ x∼y \end{matrix}} (f(x) − f(y))^{2} .

Also, var f = \frac{1}{2n^{2}} ∑_{(x,y)} (f(x) − f(y))^{2} (exercise).

If we denote by G-var f the quantity \frac{1}{2dn} ∑_{(x,y):x∼y} (f(x) − f(y))^{2}, this shows that the spectral gap is at least δ if G-var f ≥ δ var f for every f such that ∑_{x} f(x) = 0 and hence for all f.

So we have shown:

Lemma 4. Let G be a d-regular graph. Then the spectral gap, 1 − λ_{1}, is given by

1 − λ_{1} = inf_{f} \frac{G-var f}{var f} ,

where the infimum is taken over all non-constant f : V (G) → ℝ.

Proposition 5 (Discrete Poincaré Inequality (Diaconis, Stroock)). Let G be a d-regular graph with n vertices. Suppose that there is a system P of directed paths with the following properties:

• for every pair (x, y) there is a path P_{xy} ∈ P from x to y of length at most m; and

• no (directed) edge appears in more than t of the paths.

Then the spectral gap is at least \frac{n}{mtd}.

Proof. Let f : V (G) → ℝ be any function. Then (writing e_{−} for the startvertex and e_{+} for the end-vertex of an edge e)

var f = \frac{1}{2n^{2}} ∑_{(x,y)}(f(x) − f(y))^{2}

= \frac{1}{2n^{2}} ∑_{(x,y)} ( ∑_{e∈P_{xy}}(f(e_{+}) − f(e_{−})))^{2}

≤ \frac{1}{2n^{2}} ∑_{(x,y)} |P_{xy}| ∑_{e∈P_{xy}}(f(e_{+}) − f(e_{−}))^{2} (Cauchy-Schwarz)
≤ \frac{m}{2n^{2}} ∑_{e} ∑_{P_{xy}∋e}(f(e_{+}) − f(e_{−}))^{2}

≤ \frac{mtd}{n} · \frac{1}{2dn} ∑_{e}(f(e_{+}) − f(e_{−}))^{2}
= \frac{mtd}{n} G-var f.

Example. Let G be the discrete n-dimensional cube. Given two vertices A and B (which are subsets of [n]), define a path A = A_{0}, A_{1}, …, A_{n} = B as follows:

• if k ∈ B then A_{k} = A_{k−1} ∪ {k};

• if k ∉ B then A_{k} = A_{k−1} − {k}.

Now let CD be an edge of the graph G and suppose that C and D differ only in the kth place. If CD belongs to the path P_{AB} then

A ∩ {k + 1, k + 2, …, n} = D ∩ {k + 1, k + 2, …, n}

and

B ∩ {1, 2, …, k} = D ∩ {1, 2, …, k}.

Hence the number of pairs (A, B) with CD ∈ P_{AB} is at most 2^{k}2^{n−k} = 2^{n}, i.e. we can take t = 2^{n}.

So the spectral gap is at least \frac{2^{n}}{n2^{n}n} = \frac{1}{n^{2}} . Note that this is a good estimate but is not best possible.

Alternative way to see that t = 2^{n}: note that, given CD, the pair (A, B) is determined by A ∩ {1, 2, …, k} and B ∩ {k + 1, k + 2, …, n}. So we can define a surjection from ℙ[n] to {(A, B) : CD ∈ P_{AB}} by

E ↦ ((E ∩ [1, k]) ∪ (D ∩ [k + 1, n]), (D ∩ [1, k]) ∪ (E ∩ [k + 1, n]))

(where for integers a and b, [a, b] denotes the set {a, a + 1, …, b}). So t = |V (G)|.

Approximating the permanent

Let A be an n × n matrix. The permanent of A is ∑_{π∈S_{n}} ∏_{i=1}^{n} A_{iπ(i)}, i.e. “det A without the signs”.

We shall restrict attention to 01-matrices. There is a natural correspondence between these and bipartite graphs, with an edge from i to j if A_{ij} = 1.

The product ∏_{i=1}^{n} A_{iπ(i)} = 1 iff all the edges iπ(i) belong to the graph G, so the permanent of A is the number of perfect matchings in G.

Two ideas lie behind the proof to follow:

1. If you can efficiently generate a random matching in the graph (from the uniform distribution) then you can do approximate counting with high probability.

2. To do (1), devise a random walk in the space of all matchings and show that it mixes rapidly.

We shall restrict attention to dense bipartite graphs—i.e. ones where the minimum degree is at least \frac{n}{2}. (It is still #P -hard to calculate the number of matchings exactly.)

Broder’s Algorithm

Let G be a dense bipartite graph with n vertices on each side, let M be the set of perfect matchings in G and let M′ be the set of near-perfect matchings— i.e. those matchings with exactly one vertex unmatched on each side. Let N = M ∪ M′.

We define a random walk on N as follows: given M ∈ N, choose an edge e ∈ G, e = uv, uniformly at random, and do the following:

(i) if M ∈ M and e ∈ M then remove e;

(ii) if M ∈ M′ and u, v are unmatched in M then add e;

(iii) if M ∈ M′, u is unmatched in M, and v is matched to w then replace the edge wv by e;

(iv) similarly if u is matched and v is not;

(v) otherwise, do nothing.

We can define a corresponding graph on N (with several loops at each vertex) which is regular of degree |E(G)|.

Defining a system of paths

First we show how to get from M′ ∈ M′ to some M ∈ M. Let u and v be the unmatched vertices in M′. If uv ∈ E(G) then let M = M′∪{uv}. Otherwise, u must have a neighbour y and v a neighbour x such that xy ∈ M′. Pick such a pair and move to a matching M in two steps as follows: first, replaced xy by uy and then add in the edge xv. From this matching M, we can recover M′ if we are told what u and v were, so at most n^{2} of the M′ ∈ M′ end up at M. This also shows that |M′| ≤ n^{2}|M|.

Now we shall see how to get from a matching M_{1} to a matching M_{2}. First, put an arbitrary total ordering on the set of all cycles in G, and for each cycle pick a “start” vertex. The symmetric difference of M_{1} and M_{2} is a disjoint union of cycles. For each of these cycles in turn, we do the following. First, remove the edge of M_{1} incident to the start-vertex. Next, keep replacing edges of M_{1} by edges of M_{2} wherever possible. When all edges belong to M_{2}, add in the M_{2}-edge incident to the start-vertex.

Bounding the bottleneck parameter

How many pairs (M_{1}, M_{2}) use any given transition MN in the path just defined? We cannot hope to say, but we can try to bound the ratio of this to |N |. We shall do that by showing that the extra information needed to recover (M_{1}, M_{2}) if you know MN is in 1-1 correspondence with a subset of N.

Suppose that the transition MN lies in the path from M_{1} to M_{2}, where M and N are near-matchings, and M_{1} and M_{2} are perfect matchings. If we know MN and M_{1}ΔM_{2} (the union of the cycles included in the path from M_{1} to M_{2}), then we can certainly determine M_{1} and M_{2}. We can determine M_{1}ΔM_{2} from M_{1}ΔM_{2}Δ(M ∪N). However, this will not be a near-matching. But it can be made into a near-matching by the removal of one edge, and we can reconstruct the union of cycles from it with this edge removed. Similar arguments work for the other kinds of transition so the number of paths using MN is at most |N | for any transition MN.

Since any matching in M is connected to at most n^{2} near-matchings by the paths discussed earlier, we can get from any point in N to any other with each edge used at most 2n^{4}|N | times. The paths have length at most 2n and the degree of each vertex in the graph on N is at most n^{2}. So the spectral gap is at most \frac{|N |}{2n.n^{2}.2n^{4}|N |} = \frac{1}{4n^{7}} . So the walk mixes in polynomial time.

Random sampling ⇝ approximate counting

Suppose we know how to sample uniformly at random from N (G). We can use this to estimate |M(G)|/|N (G ∪ {e})| as follows.

Sample repeatedly from N (G ∪ {e}) and count how many times you get an element of M(G). For this to work, it is important that |N (G ∪ {e})| is not too much larger than |M(G)|. Any matching in G ∪ {e} is either a matching in G or the union of {e} and a near-matching in G. So

|M(G ∪ {e})| ≤ |N (G)| ≤ (n^{2} + 1)|M(G)|

and so

|N (G ∪ {e})| ≤ (n^{2} + 1)^{2}|M(G)|.

By the same argument we can estimate |N (G∪{e})|/|N (G∪{e, e′})| and so on. Since we know |N (K_{n,n})| exactly, the size of M(G) can be calculated from at most n^{2} ratios.

We have to make sure that the sum of the error probabilities is small, and that the product of the errors in the ratio estimates is small. This can easily be achieved in polynomial time.

Coupling

This is another technique for proving rapid mixing that works for some very symmetric walks.

Example. The cube. Think of it as 01-sequences of length n. Define two random walks x_{0}, x_{1}, x_{2}, … and y_{0}, y_{1}, y_{2}, … as follows. Let x_{0} be a fixed vertex and y_{0} a random vertex. At time t, choose uniformly at random from {1, 2, …, n} and randomly decide whether to take (x_{t})_{i} and (y_{t})_{i} to be 0 or 1 (but making the same decision for both), and leave the other coordinates the same as they were for x_{t−1} and y_{t−1}. What do we know about these walks?

(i) Individually, the walks (x_{t}) and (y_{t}) are the usual walks with holding probability \frac{1}{2};

(ii) y_{t} is uniformly distributed for all t;

(iii) if each i has been chosen then x_{t} = y_{t}.

The probability that some i has not been chosen by time t is at most n(1 − 1/n)^{t} ≤ e^{log n−t/n}, which is small for t ≫ n log n. So the mixing time is roughly n log n.

2 Quasirandom graphs

If G is a graph and x ∈ V (G) then we shall write N_{x} for the set of neighbours of x.

Theorem 6. Let G be an \frac{N}{2} -regular bipartite graph with vertex sets X and Y of size N. Then the following statements are equivalent, in the sense that c_{i} → 0 ⟹ c_{j} → 0.

(i) ∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} ≤ \frac{N^{4}}{16} + c_{1}N^{4}.

(ii) The number of labelled 4-cycles (x, y, x′, y′) in G with x, x′ ∈ X and y, y′ ∈ Y is at most \frac{N^{4}}{16} + c_{1}N^{4}.

(iii) ||N_{x} ∩ N_{x′}| − \frac{N}{4} | ≤ c_{2}N for all but at most c_{2}N^{2} pairs (x, x′) ∈ X^{2}.

(iv) For every A ⊂ X and B ⊂ Y, the number of edges from A to B differs from \frac{1}{2}|A||B| by at most c_{3}N^{2}.

Proof. (i) ⟺ (ii). This follows from the fact that |N_{x} ∩N_{x′}|^{2} is the number of pairs (y, y′) ∈ Y^{2} such that (x, y, x′, y′) is a labelled 4-cycle of the required kind.

(i) ⟹ (iii). Assume (i) and consider the sum

∑_{x,x′∈X} (|N_{x} ∩ N_{x′}| − \frac{N}{4} )^{2} = ∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} − \frac{N}{2} ∑_{x,x′∈X} |N_{x} ∩ N_{x′}| + \frac{N^{4}}{16} .

Now

∑_{x,x′∈X} |N_{x} ∩ N_{x′}| = ∑_{y∈Y} |N_{y}|^{2} ≥ N^{−1}( ∑_{y∈Y} |N_{y}|)^{2} = \frac{N^{3}}{4} .

Hence the original sum is at most \frac{N^{4}}{16} + c_{1}N^{4} − \frac{N^{4}}{8} + \frac{N^{4}}{16} = c_{1}N^{4}. So

||N_{x} ∩ N_{x′}| − \frac{N}{4} | > c1^{\frac{1}{3}} N for at most c1^{\frac{1}{3}} N^{2} pairs (x, x′).

(iii) ⟹ (i). If (iii) holds then

∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} ≤ N^{2} (\frac{N}{4} + c_{2}N)^{2} + c_{2}N^{2}.N^{2}

= \frac{N^{4}}{16} + (\frac{1}{2}c_{2} + c_{2}^{2} + c_{2}) N^{4}.

(i) ⟹ (iv). Let

G(x, y) = \{ \begin{matrix}1 & xy ∈ E(G) \\ 0 & otherwise \end{matrix}

and let

f(x, y) = G(x, y) − \frac{1}{2} = \{ \begin{matrix}\frac{1}{2} & xy ∈ E(G) \\ −\frac{1}{2} & otherwise \end{matrix} .

Then the left-hand side of (i) is

∑_{x,x′∈X} ∑_{y,y′∈Y} G(x, y)G(x, y′)G(x′, y)G(x′, y′)

= ∑_{x,x′∈X} ∑_{y,y′∈Y} (\frac{1}{2} + f(x, y)) (\frac{1}{2} + f(x, y′)) (\frac{1}{2} + f(x′, y)) (\frac{1}{2} + f(x′, y′))

= \frac{N^{4}}{16} + ∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)f(x, y′)f(x′, y)f(x′, y′).

All the other 14 terms are zero. For example,

∑_{x,x′∈X} ∑_{y,y′∈Y} \frac{1}{2}f(x, y′)f(x′, y)f(x′, y′) = \frac{1}{2} ∑_{x′∈X} ∑_{y,y′∈Y} f(x′, y)f(x′, y′) ∑_{x∈X} f(x, y′)
= 0

as ∑_{x∈X} f(x, y′) = 0 for all y′ ∈ Y.

So now let us assume that (iv) is false, and obtain a lower bound for ∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)f(x, y′)f(x′, y)f(x′, y′). It is

∑_{x,x′∈X} ( ∑_{y∈Y} f(x, y)f(x′, y))^{2} ≥ ∑_{x,x′∈A} ( ∑_{y∈Y} f(x, y)f(x′, y))^{2}
= ∑_{x,x′∈A} ∑_{y,y′∈Y} f(x, y)f(x, y′)f(x′, y)f(x′, y′)

= ∑_{y,y′∈Y} ( ∑_{x∈A} f(x, y)f(x, y′))^{2}

≥ ∑_{y,y′∈B} ( ∑_{x∈A} f(x, y)f(x, y′))^{2}

≥ |B|^{−2}( ∑_{y,y′∈B} ∑_{x∈A} f(x, y)f(x, y′))^{2}

= |B|^{−2} (∑_{x∈A} ( ∑_{y∈B} f(x, y))^{2})^{2}

≥ |B|^{−2} (|A|^{−1}( ∑_{x∈A} ∑_{y∈B} f(x, y))^{2})^{2}

= |A|^{−2}|B|^{−2}( ∑_{x∈A} ∑_{y∈B} f(x, y))^{4}

= |A|^{−2}|B|^{−2} (|E(A, B)| − \frac{1}{2}|A||B|)^{4}
≥ |A|^{−2}|B|^{−2}(c_{3}N^{2})^{4}
≥ c_{3}^{4}N^{4}.

Hence

∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} ≥ \frac{N^{4}}{16} + c_{3}^{4}N^{4}.

(iv) ⟹ (i). Choose an edge xy randomly from G and consider the number of edges from N_{y} ⊂ X to N_{x} ⊂ Y, assuming ∑_{x,x′∈X} |N_{x}∩N_{x′}|^{2} > \frac{N^{4}}{16} +c_{1}N^{4}. On average it is

\frac{2}{N^{2}} ∑_{xy∈E(G)} ∑_{\begin{matrix}y′∈N_{x} \\ x′∈N_{y} \end{matrix}} 1_{x′y′∈E(G)} = \frac{2}{N^{2}} ∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2}

> \frac{N^{2}}{8} + 2c_{1}N^{2}
= \frac{1}{2}|N_{x}||N_{y}| + 2c_{1}N^{2}.

Hence there exist x and y such that this is true.

Lemma 7. Let G be a bipartite graph with vertex sets X and Y of size N, with N even. Suppose that |deg(x) − \frac{N}{2} | ≤ cN for all but at most cN vertices x ∈ X ∪ Y. Then there is an \frac{N}{2} -regular graph H with |E(H)ΔE(G)| ≤ 21cN^{2}.

Proof. We can remove fewer than 2cN^{2} + cN^{2} = 3cN^{2} edges to obtain a graph with all degrees at most \frac{N}{2} and having at least

\frac{N^{2}}{2} − 2cN^{2} − cN^{2} − 3cN^{2} = \frac{N^{2}}{2} − 6cN^{2}

edges. Now add edges for as long as possible while keeping the maximum degree at most \frac{N}{2} .

If we can no longer do this, then every vertex in X of degree less than \frac{N}{2} is joined to every vertex in Y of degree less than \frac{N}{2} . Pick x ∈ X and y ∈ Y, each of degree less than \frac{N}{2} . Choose z ∈ X not joined to y. Since deg z = \frac{N}{2} (as it is not joined to y) and deg x < \frac{N}{2} , we can find w joined to z but not x. Now replace the edge zw by the edges xw and zy. The degrees of w and z stay the same, while those of x and y go up by 1. We have only changed 3 edges and increased the total number of edges by 1. So at most 18cN^{2} further changes are necessary.

Theorem 8. Let G be an \frac{N}{2} -regular graph with N vertices. Then the following statements are equivalent:

(i) ∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} ≤ \frac{N^{4}}{16} + c_{1}N^{4}.
(ii) The number of labelled 4-cycles is at most \frac{N^{4}}{16} + c_{1}N^{4}.
(iii) ||N_{x} ∩ N_{x′}| − \frac{N}{4} | ≤ c_{2}N for all but at most c_{2}N^{2} pairs (x, x′).
(iv) |E(A, B) − \frac{1}{2}|A||B|| ≤ c_{3}N^{2} for all A, B ⊂ X.

(v) |E(A, A) − \frac{1}{2}|A|^{2}| ≤ c_{4}N^{2} for every A ⊂ X.

(vi) The second-largest eigenvalue of the adjacency matrix is at most c_{5}N.

(vii) Let H be any fixed graph with k vertices and let ϕ : V (H) → V (G) be a random function. Let E be the event that ϕ(x)ϕ(y) ∈ E(G) precisely when xy ∈ E(H). Then |ℙ(E) − 2^{−\binom{k}{2}}| ≤ c_{6}.

Proof. (i) ⟺ (ii) ⟺ (iii) ⟺ (iv) by Theorem 6. (Make G into a bipartite graph by doubling up the vertex set.) Trivially (iv) ⟹ (v) and (vii) ⟹ (ii).

(v) ⟹ (iv). Let A, B be such that |e(A, B) − \frac{1}{2}|A||B|| > c_{3}N^{2}. Note that

2e(A, B) = e(A∪B, A∪B)−e(A−B, A−B)−e(B−A, B−A)+e(A∩B, A∩B).

Also,

|A||B| = \frac{1}{2}|A ∪ B|^{2} − \frac{1}{2}|A − B|^{2} − \frac{1}{2}|B − A|^{2} + \frac{1}{2}|A ∩ B|^{2}.

Hence there is some set C such that |e(C, C) − \frac{1}{2}|C|^{2}| ≥ \frac{c_{3}N^{2}}{2} .

(i) ⟺ (vi). Suppose we write

G(x, y) = ∑_{i=0}^{N−1} λ_{i}u_{i}(x)u_{i}(y)

where u_{0},u_{1}, …, u_{N−1} is an orthonormal basis of eigenvectors (of the adjacency matrix G) and λ_{0}, λ_{1}, …, λ_{N−1} are the eigenvalues with λ_{0} = \frac{N}{2} . Then

∑_{x,y∈V (G)} G(x, y) = ∑_{x,y∈V (G)} G(x, y)^{2}

= ∑_{x,y∈V (G)} ( ∑_{i=0}^{N−1} λ_{i}u_{i}(x)u_{i}(y))^{2}

= ∑_{i=0}^{N−1} ∑_{j=0}^{N−1} λ_{i}λ_{j} ∑_{x,y∈V (G)} u_{i}(x)u_{i}(y)u_{j}(x)u_{j}(y)

= ∑_{i=0}^{N−1} λ_{i}^{2}

(as ∑_{x∈V (G)} u_{i}(x)u_{j}(x) = δ_{ij}). Also,

∑_{x,y,z,w∈V (G)} G(x, y)G(y, z)G(z, w)G(w, x)

= ∑_{0≤i,j,k,l≤N−1} λ_{i}λ_{j}λ_{k}λ_{l} ∑_{x,y,z,w∈G(v)} u_{i}(x)u_{i}(y)u_{j}(y)u_{j}(z)u_{k}(z)u_{k}(w)u_{l}(w)u_{l}(x)
= ∑_{0≤i,j,k,l≤N−1} λ_{i}λ_{j}λ_{k}λ_{l}⟨u_{i}, u_{l}⟩⟨u_{i}, u_{j}⟩⟨u_{j}, u_{k}⟩⟨u_{k}, u_{l}⟩

= ∑_{i=0}^{N−1} λ_{i}^{4},

i.e.

∑_{x,x′∈V (G)} |N_{x} ∩ N_{x′}|^{2} = ∑_{i=0}^{N−1} λ_{i}^{4}.

If |λ_{i}| ≤ c_{5}N for every i > 0 then

∑_{i=1}^{N−1} λ_{i}^{4} ≤ (c_{5}N)^{2} ∑_{i=0}^{N−1} λ_{i}^{2} = c_{5}^{2}N^{2} \frac{N^{2}}{2} = \frac{1}{2}c_{5}^{2}N^{4},

and so

∑_{x,x′∈V (G)} |N_{x} ∩ N_{x′}|^{2} ≤ \frac{N^{4}}{16} + \frac{1}{2}c_{5}^{2}N^{4}.

Conversely, if there is some i > 0 for which |λ_{i}| > c_{5}N, then

∑_{x,x′∈V (G)} |N_{x} ∩ N_{x′}|^{2} = ∑_{i=0}^{N−1} λ_{i}^{4} > \frac{N^{4}}{16} + c_{5}^{4}N^{4}.

(iv) ⟺ (vii). We shall, in fact, prove the following stronger result:

Let G be a k-partite graph with vertex sets X_{1}, X_{2}, …, X_{k}, all of size N = 2^{k}M, such that all the bipartite graphs spanned by (X_{i}, X_{j}), i ≠ j, are \frac{N}{2} -regular and have the property that, whenever A ⊂ X_{i} and B ⊂ X_{j}, then |e(A, B) − \frac{1}{2}|A||B|| ≤ c_{3}N^{2}. Let H be a graph with vertex set {1, 2, …, k} and let x_{i} ∈ X_{i} be chosen randomly. Then

|ℙ [x_{i}x_{j} ∈ E(G) ⟺ ij ∈ E(H)] − 2^{−\binom{k}{2}}| ≤ c_{6}

for some c_{6} that (depends on k and) tends to 0 as c_{3} → 0.

Let E be the event [x_{i}x_{j} ∈ E(G) ⟺ ij ∈ E(H)]. Pick x_{i} randomly. Then a necessary condition for E is that x_{i} ∈ N_{x_{1}} ∩ X_{i} whenever 1i ∈ E(H), and x_{i} ∈ X_{i} − N_{x_{1}} whenever 1i ∉ E(H). Let

A_{i} = \{ \begin{matrix}X_{i} ∩ N_{x_{1}} & 1i ∈ E(H) \\ X_{i} − N_{x_{1}} & 1i ∉ E(H) \end{matrix} (i = 2, 3, …, k).

Then the probability that x_{i} ∈ A_{i}, i = 2, 3, …, k, is 2^{−(k−1)}.

It remains to discuss ℙ(E|x_{i} ∈ A_{i}, i = 2, 3, …, k). First, let us show that the graph spanned by A_{i} and A_{j} is approximately regular. If there are c\frac{N}{2} vertices in A_{i} of degree greater than \frac{N}{4} + c\frac{N}{2} in A_{j} then let B be the set of these bad vertices. We have

e(B, A_{j}) > (\frac{N}{4} + c\frac{N}{2} ) |B| = \frac{1}{2}|B||A_{j}| + c\frac{N}{2} |B| ≥ \frac{1}{2}|B||A_{j}| + \frac{c^{2}}{4} N^{2},

contradicting our assumption if c ≥ 2\sqrt{c_{3}}. We may proceed similarly if c\frac{N}{2} have degree less than \frac{N}{4} − c\frac{N}{2} .

So, we can make the graph spanned by A_{i} and A_{j} become \frac{N}{4} -regular after changing at most 84\sqrt{c_{3}} (\frac{N}{2} )^{2} edges. In the modified graph, if A ⊂ A_{i} and B ⊂ A_{j} then

|e(A, B) − \frac{1}{2}|A||B|| ≤ (c_{3} + 21\sqrt{c_{3}}) N^{2} ≤ 100\sqrt{c_{3}} (\frac{N}{2} )^{2}

(if \sqrt{c_{3}} ≥ c_{3}).

By induction, the probability that x_{i}x_{j} is an edge of the modified graph precisely when ij is an edge of H given that x_{i} ∈ A_{i} for i = 2, 3, …, k differs from 2^{−\binom{(k−1)}{2}} by at most c, where c → 0 as 100\sqrt{c_{3}} → 0. The probability that some x_{i}x_{j} is a modified edge is at most 84\sqrt{c_{3}}\binom{k−1}{2} → 0 so ℙ(E) − 2^{−(k−1)}2^{−\binom{k−1}{2}} → 0 as c_{3} → 0.

Lemma 9. Let V and W be two n-dimensional real inner product spaces, and let α : V → W be a linear map. Then α can be written ∑_{i=0}^{n−1} λ_{i}v_{i} ⊗ w_{i}, where (v_{i})_{i=0}^{n−1} and (w_{i})_{i=0}^{n−1} are orthonormal bases and v⊗w denotes the rank-1 map u ↦ ⟨u, v⟩w.

Proof. Pick v ∈ V and w ∈ W with ∥v∥ = ∥w∥ = 1 so as to maximize ⟨αv, w⟩. Clearly w = \frac{αv}{∥αv∥} and then ⟨αv, w⟩ = ∥αv∥, so we are looking for v

that maximizes \frac{∥αv∥}{∥v∥}.

If we have this v and ⟨u, v⟩ = 0, then ∥v + δu∥^{2} = ∥v∥^{2} + o(δ) and ∥α(v + δu)∥^{2} = ∥αv∥^{2} + 2δ⟨αu, αv⟩ + o(δ), so if ⟨αv, αu⟩ ≠ 0 we can choose a δ such that \frac{∥α(v+δu)∥}{∥v+δu∥} > \frac{∥αv∥}{∥v∥}, a contradiction. Therefore whenever ⟨u, v⟩ = 0 then also ⟨αu, αv⟩ = 0.

Set v_{0} = v, w_{0} = \frac{αv}{∥αv∥}, V_{1} = ⟨v_{0}⟩^{⊥} and W_{1} = ⟨w_{0}⟩^{⊥}. Then α : V_{1} → W_{1}, so, by induction, we can write the restriction of α to V_{1} as ∑_{i=1}^{n−1} λ_{i}v_{i} ⊗ w_{i}, where (v_{i})_{i=1}^{n−1} and (w_{i})_{i=1}^{n−1} are orthonormal and all the v_{i} are orthogonal to v_{0} and all the w_{i} are orthogonal to w_{0}.

It is not hard to show that if we apply this decomposition to the (bipartite) adjacency matrix of a bipartite graph G with n + n vertices then the number of labelled 4-cycles (x, y, x′, y′) with x, x′ ∈ X is ∑_{i=0}^{n−1} λ_{i}^{4}. So, as with graphs, if G is \frac{n}{2}-regular, we can say that G is quasirandom iff for all i > 0, |λ_{i}| ≤ cn for small c. Since λ_{0} = \frac{n}{2} and v_{0} = w_{0} = \frac{1}{\sqrt{n}}(1, 1, …, 1), this says that ∑_{xy∈E(G)} v(x)w(y) ≤ cn∥v∥_{2}∥w∥_{2} whenever ∑_{x∈X} v(x) = ∑_{y∈Y} w(y) = 0.

Alternatively, G(x, y) − \frac{1}{2} has small correlation with any rank-1 matrix.

3 Szemerédi’s Regularity Lemma

Let G be a graph, and let A, B ⊂ V (G). The density of the pair (A, B) is defined to be

d(A, B) = \frac{|E(A, B)|}{|A||B|} = \frac{|\{(x, y) ∈ A × B : xy ∈ E(G)\}|}{|A × B|}.

The pair is said to be ε-regular if, whenever A′ ⊂ A and B′ ⊂ B with |A′| ≥ ε|A| and |B′| ≥ ε|B|, then |d(A′, B′) − d(A, B)| ≤ ε. A partition X_{1}, X_{2}, …, X_{k} of V (G) is said to be ε-regular if

∑ \{\frac{|X_{i}||X_{j}|}{n^{2}} : (X_{i}, X_{j}) is not ε-regular\} ≤ ε.

Equivalently, the partition is ε-regular if for (x, y) ∈ V (G)^{2}, the probability that (x, y) belongs to an irregular pair is less than ε.

Theorem 10 (Szemerédi’s Regularity Lemma). Let ε > 0. Then there exists K = K(ε) such that for every graph G, there is an ε-regular partition of V (G) into at most K sets.

Definition. Given a partition X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{m} of V (G), define the meansquare density to be

∑_{i,j=1}^{m} \frac{|X_{i}||X_{j}|}{n^{2}}d(X_{i}, X_{j})^{2}.

Since ∑_{i,j=1}^{m} \frac{|X_{i}||X_{j}|}{n^{2}} = 1 and 0 ≤ d(X_{i}, X_{j}) ≤ 1, we see that the mean-square density lies between 0 and 1.

Lemma 11. Let X_{1}, X_{2}, …, X_{m} be a partition, and let Y_{1}, Y_{2}, …, Y_{M} be a partition that refines X_{1}, X_{2}, …, X_{m}. Then the mean-square density with respect to Y_{1}, Y_{2}, …, Y_{M} is at least as big as that with respect to X_{1}, X_{2}, …, X_{m}.

Proof. Suppose each X_{i} is split into X_{i1} ∪ X_{i2} ∪ ⋯ ∪ X_{ir_{i}}. Then

d(X_{i}, X_{j})^{2} = ( ∑_{s,t} \frac{|X_{is}||X_{jt}|d(X_{is}, X_{jt})}{|X_{i}||X_{j}|})^{2}

≤ ( ∑_{s,t} \frac{|X_{is}||X_{jt}|}{|X_{i}||X_{j}|})( ∑_{s,t} \frac{|X_{is}||X_{jt}|}{|X_{i}||X_{j}|}d(X_{is}, X_{jt})^{2}).

Hence

\frac{|X_{i}||X_{j}|}{n^{2}}d(X_{i}, X_{j})^{2} ≤ ∑_{s,t} \frac{|X_{is}||X_{jt}|}{n^{2}}d(X_{is}, X_{jt})^{2}.

Remark. The same proof shows (or the lemma itself implies) a similar statement for bipartite graphs: if G has vertex sets X and Y partitioned into X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{r} and Y_{1} ∪ Y_{2} ∪ ⋯ ∪ Y_{s}, and Z_{1} ∪ Z_{2} ∪ ⋯ ∪ Z_{R} and W_{1} ∪ W_{2} ∪ ⋯ ∪ W_{S} refine X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{r} and Y_{1} ∪ Y_{2} ∪ ⋯ ∪ Y_{s} respectively, then

∑_{i=1}^{r} ∑_{j=1}^{s} \frac{|X_{i}||X_{j}|}{|X||Y |}d(X_{i}, X_{j})^{2} ≤ ∑_{i=1}^{R} ∑_{j=1}^{S} \frac{|Z_{i}||W_{j}|}{|X||Y |}d(Z_{i}, W_{j})^{2}.

Lemma 12. Let (X, Y) be some pair of sets of vertices in a graph G, and suppose that d(X, Y) = α and (X, Y) is not ε-regular. Then there are partitions X = X_{1} ∪ X_{2} and Y = Y_{1} ∪ Y_{2} such that

∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}d(X_{i}, Y_{j})^{2} ≥ α^{2} + ε^{4}.

Proof. By the non-ε-regularity, we can find X_{1} ⊂ X and Y_{1} ⊂ Y such that |d(X_{1}, Y_{1})−α| ≥ ε and |X_{1}| ≥ ε|X|, |Y_{1}| ≥ ε|Y |. Let u(X_{i}, Y_{i}) = d(X_{i}, Y_{i})−α. Then

ε^{4} ≤ ∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}u(X_{i}, Y_{j})^{2}

= ∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}d(X_{i}, Y_{j})^{2} − 2α ∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}d(X_{i}, Y_{j}) + α^{2} ∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}

= ∑_{i,j=1}^{2} \frac{|X_{i}||Y_{j}|}{|X||Y |}d(X_{i}, Y_{j})^{2} − α^{2}.

Lemma 13. Let G be a graph with N vertices, and let X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{m} be a partition of the vertices that is not ε-regular. Then there is a refinement X_{11} ∪ ⋯ ∪ X_{1r_{1}} ∪ X_{21} ∪ ⋯ ∪ X_{2r_{2}} ∪ ⋯ ∪ X_{m1} ∪ ⋯ ∪ X_{mr_{m}} such that each r_{i} is at most 2^{2m} and the mean-square density is bigger by at least ε^{5}.

Proof. Let I = {(i, j) : (X_{i}, X_{j}) is not ε-regular}. Let α^{2} be the mean-square density of G with respect to X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{m}.

For each (i, j) ∈ I, Lemma 12 gives us partitions X_{i} = A_{1}^{ij} ∪ A_{2}^{ij} and X_{j} = B_{1}^{ij} ∪ B_{2}^{ij} such that

∑_{p,q=1}^{2} \frac{|A_{p}^{ij}||B_{q}^{ij}|}{|X_{i}||X_{j}|}d(A_{p}^{ij}, B_{q}^{ij})^{2} ≥ d(X_{i}, X_{j})^{2} + ε^{4}.

Now, for each i, let X_{i1} ∪ X_{i2} ∪ ⋯ ∪ X_{ir_{i}} be a partition of X_{i} into at most 2^{2m} sets such that every A_{1}^{ij}, A_{2}^{ij}, B_{1}^{ij} and B_{2}^{ij} is a union of some of the X_{ih}. Then, by Lemma 11 (and the remark after it),

∑_{p=1}^{r_{i}} ∑_{q=1}^{r_{j}} \frac{|X_{ip}||X_{jq}|}{|X_{i}||X_{j}|}d(X_{ip}, X_{jq})^{2} ≥ d(X_{i}, X_{j})^{2} + ε^{4}

for all (i, j) ∈ I. Multiplying both side by \frac{|X_{i}||X_{j}|}{N^{2}} and summing over all (i, j), splitting into a sum over I and a sum over I^{c}, we have

∑_{i,j=1}^{m} ∑_{p=1}^{r_{i}} ∑_{q=1}^{r_{j}} \frac{|X_{ip}||X_{jq}|}{N^{2}}d(X_{ip}, X_{jq})^{2} ≥ ∑_{i,j=1}^{m} \frac{|X_{i}||X_{j}|}{N^{2}}d(X_{i}, X_{j})^{2} + ε^{4} ∑_{(i,j)∈I} \frac{|X_{i}||X_{j}|}{N^{2}}
≥ α^{2} + ε^{5}.

Proof (of Theorem 10). Start with the trivial partition of V (G) into one set. If it is ε-regular then we are done. If not, refine it into at most four sets in such a way that mean-square density increases by ε^{5}.

Continue this process. If at stage k we have a partition into m sets then at stage k + 1 we have one into at most m.2^{2m} ≤ 2^{2^{m}}. Hence the process must stop at an ε-regular partition after at most ε^{−5} steps. The number of

cells in the final partition is therefore at most 2^{2^{2^{·^{·^{·^{2}}}}}} ^{}2ε^{−5}}.

Lemma 14. Let G be a graph, and let X, Y, Z ⊂ V (G). Suppose that (X, Y), (Y, Z) and (X, Z) are ε-regular and that d(X, Y) = α, d(Y, Z) = β and d(X, Z) = γ. Then the number of (x, y, z) ∈ X ×Y ×Z forming triangles in G is at least (1 − 2ε)(α − ε)(β − ε)(γ − ε)|X||Y ||Z|, provided α, β, γ ≥ 2ε.

Proof. For each x ∈ X, write d_{Y} (x) for |N_{x} ∩ Y | and d_{Z}(x) for |N_{x} ∩ Z|. Then the number of x ∈ X such that d_{Y} (x) < (α − ε)|Y | is at most ε|X| by ε-regularity of (X, Y). Similarly, at most ε|X| of the x ∈ X have d_{Z}(x) < (β − ε)|Z|. If d_{Y} (x) ≥ (α − ε)|Y | and d_{Z}(x) ≥ (β − ε)|Z| then, by ε-regularity of (Y, Z), the number of edges between N_{x} ∩ Y and N_{x} ∩ Z is at least (γ − ε)(α − ε)(β − ε)|Y ||Z|. Summing over x ∈ X gives the result.

Theorem 15. For all ε > 0, there exists some δ > 0 with the following property: given any graph G with n vertices and at most δn^{3} triangles, it is possible to remove at most εn^{2} edges from G to make it triangle-free.

Proof. Let X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{M} be an \frac{ε}{4}-regular partition with M ≤ M(ε). From G, remove the edge xy if

(i) (x, y) ∈ X_{i} × X_{j} with (X_{i}, X_{j}) not an \frac{ε}{4}-regular pair; or
(ii) (x, y) ∈ X_{i} × X_{j} with d(X_{i}, X_{j}) < \frac{ε}{2}; or
(iii) x ∈ X_{i} with |X_{i}| ≤ \frac{εn}{4M}.

The number of edges removed by (i) is at most ∑_{(i,j)∈I} |X_{i}||X_{j}| ≤ \frac{εn^{2}}{4} , since the partition is \frac{ε}{4}-regular. The number removed by (ii) is at most ∑_{i,j} \frac{ε}{2}|X_{i}||X_{j}| = \frac{εn^{2}}{2} . The number removed by (iii) is at most Mn\frac{εn}{4M} = \frac{εn^{2}}{4} .

Now suppose that, after these edges have been removed, there is still a triangle (x, y, z) ∈ X_{i} × X_{j} × X_{k}, say. Then the pairs (X_{i}, X_{j}), (X_{j}, X_{k}) and (X_{i}, X_{k}) are all \frac{ε}{4}-regular with density at least \frac{ε}{2} (or we would have removed these edges). Also |X_{i}|, |X_{j}|, |X_{k}| > \frac{εn}{4M}. By Lemma 14, G contains at least (1 − \frac{ε}{2}) (\frac{ε}{4})^{3} (\frac{εN}{4M} )^{3} labelled triangles. So let δ = \frac{ε^{6}}{2^{20}M^{3}} and the result is proved.

Theorem 16. Let δ > 0. Then there exists N_{0} such that if N ≥ N_{0} and A ⊂ [N]^{2} with |A| ≥ δN^{2} then A contains a triple of the form (x, y), (x+d, y), (x, y + d) with d > 0.

Proof. The set A + A = {x + y : x, y ∈ A} is contained in [2N]^{2} so there must exists z that can be written as x + y in at least \frac{(δN^{2})^{2}}{(2N)^{2}} = \frac{δ^{2}N^{2}}{4} ways. Pick such a z and write A′ = A ∩ (z − A) and δ′ = \frac{δ^{2}}{4} . Then A′ has size at least δ′N^{2} and has the property that if A′ contains a triple of the form (x, y), (x + d, y), (x, y + d) for d < 0 then so does z − A, and hence A contains such a triple with d > 0. So, replacing A by A′ and δ by δ′, we may assume that A contains no such triple for d ≠ 0.

Now, we construct a tripartite graph as follows. The vertex sets are X = [N], Y = [N] and Z = [2N]. Think of X as the set of vertical lines through A, Y as the set of horizontal lines, and Z as the set of diagonal lines with x + y constant. Join x ∈ X to y ∈ Y iff (x, y) ∈ A, join x ∈ X to z ∈ Z iff (x, z − x) ∈ A and join y ∈ Y to z ∈ Z iff (z − y, y) ∈ A (i.e. join two lines iff their intersection is in A).

Suppose G contains a triangle (x, y, z). Then (x, y), (x, y + (z − x − y)) and (x + (z − x − y), y) are all in A, which is a contradiction unless x + y = z (which is the degenerate case where the three lines meet in a point). So G has at most N^{2} = \frac{1}{64N} (4N)^{3} triangles. So for sufficiently large N, we can remove at most \frac{δN^{2}}{2} edges from G to make it triangle-free. However, the degenerate triangles are edge-disjoint (since any edge in G determines a unique point of A) and there are at least δN^{2} of them. So we have a contradiction.

Corollary 17. Let δ > 0. Then if N is sufficiently large and A ⊂ [N] is any set of size at least δN, A contains an arithmetic progression of length 3.

Proof. Define a subset B ⊂ [2N]^{2} to be {(x, y) : y−x ∈ A}. Then |B| ≥ δN^{2}, so by Theorem 16 we can find x, y, and d ≠ 0 such that y − (x + d), y − x and y + d − x all belong to A.

Theorem 18 (Erdős-Stone Theorem). Let H be a graph with chromatic number k. Then a graph G with n vertices that contains no copy of H has at most (1 − \frac{1}{k−1}) \binom{n}{2}(1 + o(1)) edges (and this is best possible).

Proof (sketch). The example of a complete (k − 1)-partite graph with vertex subsets of roughly equal size shows that the estimate cannot be substantially improved.

Conversely, suppose that G contains no copy of H. Let X_{1}, X_{2}, …, X_{M} be an ε-regular partition of V (G) for some small ε > 0. Remove edges xy if they belong to sparse or irregular pairs X_{i} ×X_{j}, or pairs with X_{i} or X_{j} small. Not too many edges are removed. Let G′ be G with these edges removed.

If G′ contains a K_{k} then, by a generalization of the lemma counting triangles, the resulting k-partite subgraph contains several copies of H.

(The resulting lemma says that if you randomly embed V (H) into a k-partite graph with all pairs regular, respecting the k-partition of V (H), then the probability that ϕ(x)ϕ(y) ∈ E(G) whenever xy ∈ E(H) is what it would be for random graphs of the appropriate density).

So G′ contains no K_{k}, and so by Turán’s theorem has at most (1 − \frac{1}{k−1}) \binom{n}{2} edges.

4 Crossing numbers and combinatorial geometry

Theorem 19. A planar graph with n ≥ 3 vertices has at most 3n − 6 edges.

Proof. Assume wlog G is maximal planar (and so, in particular, is connected). Then Euler’s theorem says that V − E + F = 2. It is easy to see that every face has at least 3 edges, so the number of edge-face pairs is equal to 2E and at least 3F. So F ≤ \frac{2}{3}E, giving V − \frac{E}{3} ≥ 2 and so E ≤ 3V − 6.

Lemma 20. Let G be a graph with n vertices and m ≥ 4n edges. Then any drawing of G in ℝ^{2} must have at least \frac{m^{3}}{64n^{2}} crossings.

Proof. First, note that the number of crossings is at least m − (3n − 6). To see this, let G have m > 3n−6 edges. Remove an edge involved in a crossing (which exists by Theorem 19). The number of crossings goes down by at least 1. We can do this m − (3n − 6) times.

Now let 0 < p ≤ 1 and choose vertices independently and randomly with probability p, forming an induced subgraph H. Suppose that G has been drawn with t crossings. Then the expected number of vertices of H is pn, the expected number of edges is p^{2}m and the expected number of crossings is p^{4}t. Also, the expected number of crossings is at least p^{2}m − 3pn. So choose p such that p^{2}m = 4pn, i.e. take p = \frac{4n}{m} (which by assumption is at most 1). Then p^{4}t ≥ pn, giving t ≥ \frac{n}{p^{3}} = \frac{m^{3}}{64n^{2}} .

Definition. A pseudoline system in ℝ^{2} is a collection Λ of curves l such that any two intersect in at most one point.

Theorem 21 (Szemerédi-Trotter Theorem). Let X ⊂ ℝ^{2} be a set of n points, and let Λ be a set of m pseudolines. Then the number of pairs (x, l) such that x ∈ X, l ∈ Λ and x ∈ l, i.e. the number of incidences, is at most 8(m^{\frac{2}{3}} n^{\frac{2}{3}} + m + n).

Proof. Suppose that there are t incidences. Define a graph G with vertex set X by joining x to y iff they are adjacent along some l ∈ Λ (i.e. regard Λ as a drawing of G). Then G has at least t − m edges. If t ≥ 2m then this is at least \frac{t}{2}. If t ≥ 2m and \frac{t}{2} ≥ 4n then there are at least \frac{t^{3}}{512n^{2}} crossings by Lemma 20. But since Λ is a pseudoline system, there are at most \binom{m}{2} ≤ m^{2} crossings. So t^{3} ≤ 512n^{2}m^{2}, and so t ≤ 8m^{\frac{2}{3}} n^{\frac{2}{3}} .

We have shown t ≥ max\{2m, 8n\} ⟹ t ≤ 8m^{\frac{2}{3}} n^{\frac{2}{3}} .

Corollary 22. Let X be a set of n points, and Λ a pseudoline system with each l ∈ Λ containing at least k ≥ 2 points of X. Then |Λ| ≤ C max \{\frac{n^{2}}{k^{3}} , \frac{n}{k}\}.

Proof. Let |Λ| = m. Then the number of incidences is at least mk. So mk ≤ 8(m^{\frac{2}{3}} n^{\frac{2}{3}} + m + n) ≤ 16(m^{\frac{2}{3}} n^{\frac{2}{3}} + n). Hence either m^{\frac{2}{3}} n^{\frac{2}{3}} ≥ cmk or n ≥ cmk, giving m ≤ C max \{\frac{n^{2}}{k^{3}} , \frac{n}{k}\}.

Lemma 23. Let X ⊂ ℝ^{2} be a set of size n, let A ⊂ ℝ be a set of size r and let f be a strictly concave or strictly convex function defined on some interval that contains A. Let Z = {(a, f(a)) : a ∈ A} ⊂ ℝ^{2}. Then

|X + Z| ≥ c min\{n^{\frac{1}{2}} r^{\frac{3}{2}} , nr\}.

Proof. Let N = |X + Z| and let Γ be the graph of f. Then the curves x + Γ (x ∈ X) from a pseudoline system, by the convexity/concavity of f. It has size n. Each x ∈ Γ intersects X + Z in at least r points. Hence

n ≤ C max \{\frac{N^{2}}{r^{3}} , \frac{N}{r} \}

and so

N ≥ c min\{r^{\frac{3}{2}} n^{\frac{1}{2}} , rn\}.

Corollary 24. Let A, B, C ⊂ ℝ be sets of size n and let f be as above. Then |A + B||f(A) + C| ≥ cn^{\frac{5}{2}} .

Proof. We note that B × C + {(a, f(a)) : a ∈ A} ⊂ (A + B) × (f(A) + C) and so, by Lemma 23, |A + B||f(A) + C| ≥ c min\{nn^{\frac{3}{2}} , n^{2}n\} = cn^{\frac{5}{2}} .

Corollary 25. Let A be a set of size n in ℝ, and let f be a strictly convex or strictly concave function. Then

(i) either |A + A| ≥ cn^{\frac{5}{4}} or |f(A) + f(A)| ≥ cn^{\frac{5}{4}} ;
(ii) |A + f(A)| ≥ cn^{\frac{5}{4}} ;
(iii) either |A + A| ≥ cn^{\frac{5}{4}} or |A.A| ≥ cn^{\frac{5}{4}} .

Proof. (i) Setting B = A and C = f(A) in Corollary 24, and noting that |f(A)| ≥ \frac{n}{2}, we observe that |A + A||f(A) + f(A)| ≥ cn^{\frac{5}{2}} and the result follows immediately.

(ii) Set B = f(A) and C = A.

(iii) We may assume wlog that half the elements of A are positive. Let f(x) = log x. Since | log A + log A| = |A.A|, (iii) follows from (i) applied to the set {a ∈ A : a > 0}.

Theorem 26. Let X be a set of n points in ℝ^{2}. Then the number of pairs (x, y) ∈ X^{2} with d(x, y) = 1 is at most Cn^{\frac{4}{3}} .

Proof. Define a multigraph G with loops by drawing around each x ∈ X a unit circle and, for y, z ∈ X, joining y to z if they are adjacent along one of the circles drawn. If the number of unit distances is t then the number of edges is t.

Remove all circles that contain at most two points of X. So we’ve removed at most 2n edges from G. Now any two vertices are joined by at most two edges. If they are joined by precisely two then remove one of them. This removes at most half the edges.

So if t ≥ 4n then the resulting simple graph has at least \frac{t}{4} edges. If \frac{t}{4} ≥ 4n then by Lemma 20 there are at least \frac{(t/4)^{3}}{64n^{2}} = \frac{t^{3}}{4096n^{2}} crossings. But two circles cross in at most two points so the number of crossings is at most 2\binom{n}{2} ≤ n^{2}. So t^{3} ≤ 4096n^{4} and so t ≤ 16n^{\frac{4}{3}} .

Theorem 27. Let G be a multigraph with n vertices, m edges and maximum edge-multiplicity at most d. If m ≥ 32nd then the number of crossings is at least \frac{cm^{3}}{n^{2}d}.

Proof. For i = 1, 2, …, ⌊log_{2} d + 1⌋, let G_{i} be the multigraph consisting of all edges with multiplicities r such that 2^{i−1} ≤ r < 2^{i}. For each i, let the number of pairs xy that are joined in G_{i} be m_{i}. The number of edges in multigraphs G_{i} such that m_{i} < 4n is at most ∑_{i=1}^{⌊log_{2} d⌋+1} 4n.2^{i} ≤ 16nd. So if we remove these then we still have at least \frac{m}{2} edges.

Let B = {i : at least 4n pairs are joined in G_{i}}. If i ∈ B then I claim that the number of crossings in G_{i} is at least \frac{2^{2(i−1)}m_{i}^{3}}{64n^{2}} . The reason is that if we choose one edge at random from the set joining x to y (when they are joined) then the probability that any given crossing survives is at most 2^{−2(i−1)}, but the number of crossings left is at least \frac{m_{i}^{3}}{64n^{2}} by Theorem 20. So the number of crossings in G is at least ∑_{i∈B} \frac{2^{2(i−1)}m_{i}^{3}}{n^{2}} . But

\frac{m}{2} ≤ ∑_{i∈B} m_{i}2^{i} = ∑_{i∈B} 2^{\frac{2i}{3}} m_{i}2^{\frac{i}{3}} ≤ ( ∑_{i∈B} 2^{2i}m_{i}^{3})^{\frac{1}{3}} ( ∑_{i∈B} 2^{\frac{i}{2}} )^{\frac{2}{3}}

≤ C( ∑_{i∈B} 2^{2(i−1)}m_{i}^{3})^{\frac{1}{3}} d^{\frac{1}{3}} .

Hence

∑_{i∈B} \frac{2^{2(i−1)}m_{i}^{3}}{n^{2}} ≥ \frac{cm^{3}}{n^{2}d} .

Theorem 28. Let X be a set of n points in ℝ^{2}. Then X determines at least cn^{\frac{4}{5}} distinct distances.

Proof. Suppose that the number of distinct distances is t, and that these distances are r_{1}, r_{2}, …, r_{t}. About each x ∈ X, draw circles of radius r_{1}, r_{2}, …, r_{t}. Define a multigraph by joining y, z ∈ X iff they are adjacent along one of the circles drawn (once per arc with this property). We may assume throughout the proof that n is large.

The number of edges is n(n − 1) ≥ \frac{99}{100}n^{2}. If t < n^{\frac{4}{5}} then the number of edges from circles with at most two points is at most 2nt ≤ \frac{n^{2}}{100}, so remove these. Let k be an integer to be chosen (it will be n^{\frac{2}{5}} ). We now wish to bound from above the number of edges of multiplicity at least k.

The perpendicular bisector of such an edge (considered geometrically) is a line that contains at least k points of X. So we shall bound from above the number of pairs (e, l) such that e is an edge, l bisects e, and l contains u ≥ k points of X. The number of lines l with 2^{i−1} ≤ u < 2^{i} is at most C max\{\frac{n^{2}}{2^{3i}} , \frac{n}{2^{i}} \} by Corollary 22. Each such line is involved in at most 2t.2^{i} pairs (e, l), so the total number is at most

C( ∑_{k≤2^{i}≤\sqrt{n}} t\frac{n^{2}}{2^{3i}} 2^{i} + ∑_{\sqrt{n}≤2^{i}≤n} \frac{tn2^{i}}{2^{i}} ) ≤ C (t\frac{n^{2}}{k^{2}} + tn log n) .

We want this to be less than \frac{n^{2}}{4} , which is true if t ≤ n^{\frac{4}{5}} and t ≤ ck^{2}.

After removing all edges of multiplicities at least k, we still have at least \frac{n^{2}}{2} edges left, so by Theorem 27, there are at most \frac{cn^{6}}{n^{2}k} = \frac{cn^{4}}{k} crossings. But the number of crossings is also at most n^{2}t^{2}, so t^{2} ≥ \frac{cn^{2}}{k}, and so t ≥ \frac{cn}{\sqrt{k}}. So

we have shown that t ≥ c min \{k^{2}, \frac{n}{\sqrt{k}}\}. If we choose k = n^{\frac{2}{5}} , we get the result.

Theorem 29 (Beck’s two-extremities theorem). Let X be a set of n points in ℝ^{2}. Then either there are at least cn^{2} lines determined by pairs of points in X, or some line contains at least cn points.

Proof. The number of lines containing between between 2^{i} and 2^{i+1} points is at most C max \{\frac{n^{2}}{2^{3i}} , \frac{n}{2^{i}} \} by Corollary 22. Any line with this property contains at most 2^{2i+1} pairs of points of X. So the number of pairs belonging to lines that contain between A and \frac{n}{A} points of X is at most

C′ ∑_{A≤2^{i}≤ \frac{n}{A}} max \{\frac{n^{2}}{2^{i}} , 2^{i}n\} ≤ \frac{C′′n^{2}}{A} (by consideration of two geometric sums).

So choosing A = 2C′′, there must be at least \frac{n^{2}}{2} pairs belonging to lines with at least \frac{n}{A} or at most A points.

If any line contains at least \frac{n}{A} points then we are done.

Otherwise, at least \frac{n^{2}}{2} pairs belong to lines with at most A^{2} pairs, so there must be at least \frac{n^{2}}{2A^{2}} lines.

Corollary 30. Let X be any set of n points in ℝ^{2}, not all collinear. Then there must be some point x_{0} ∈ X such that there are at least cn different lines containing x_{0} and some other point of X.

Proof. If cn points lie on a line, let x_{0} be some point not on the line. Otherwise, there are at least cn^{2} lines so some point must be on at least cn of them.

Lemma 31. Let A, B ⊂ ℝ be sets of size n. Then the number of collinear triples in A × B is at most Cn^{4} log n.

Proof. By Corollary 22, the number of lines with r points of A × B for some r with 2^{i} ≤ r < 2^{i+1} is at most \frac{Cn^{4}}{2^{3i}} (since \frac{n^{2}}{2^{i}} ≤ \frac{n^{4}}{(2^{i})^{3}} as r ≤ n). Such a line contains at most C2^{3i} triples. So the number of collinear triples is at most C ∑_{2^{i}≤n} \frac{n^{4}}{2^{3i}} 2^{3i} = Cn^{4} log n.

Theorem 32. Let A ⊂ ℝ be a set of size n. Then |A + A|^{4}|A.A| ≥ \frac{cn^{6}}{log n}.

Proof. Let |A.A| = p and |A + A| = s. Then A × A is contained in the union of the p sets X_{λ} = {(x, y) : xy = λ} for λ ∈ A.A. So ∑_{λ∈A.A} |X_{λ}| ≥ n^{2}, and, by Cauchy-Schwarz, ∑_{λ∈A.A} |X_{λ}|^{2} ≥ \frac{n^{4}}{p}, so there are at least p^{−1}n^{4} pairs ((a′, b′), (a′′, b′′)) such that a′b′ = a′′b′′ (i.e. belonging to the same X_{λ}). For every (a, b) ∈ A × A and every such pair, we get a collinear triple ((a, b), (a + a′, b + b′′), (a + a′′, b + b′)) in (A ∪ (A + A)) × (A ∪ (A + A)). By Lemma 31 (and the fact that |A| ≤ |A + A| ≤ |A|^{2}), n^{2}p^{−1}n^{4} ≤ Cs^{4} log n, and so ps^{4} ≥ \frac{cn^{6}}{log n}.

Example. Let k ≤ \sqrt{n}. Let X = \{1, 2, …, k\} × \{1, 2, …, \frac{n}{k}\}. Then any line y = mx + b with m, b ∈ ℕ, b ≤ \frac{n}{2k} and m ≤ \frac{n}{2k^{2}} goes through k points of X, and there are \frac{cn^{2}}{k^{3}} of them. On the other hand, if k ≥ \sqrt{n} then pick any \frac{n}{k} lines and put k points on each. This shows that Corollary 22 is tight.

5 Monotone Circuit Complexity

A circuit is a directed, acyclic graph with different kinds of vertices called inputs, outputs, AND gates, OR gates, and NOT gates with the following properties:

(i) x is an input iff it has in-degree zero;

(ii) x is an output iff it has out-degree zero;

(iii) x is a NOT gate iff it has in-degree 1;

(iv) x may be both an output and a gate.

Let f be a function from the set I of inputs of some circuit C to the set {0, 1}. Then there is a unique extension g of f to V (C) such that

(i) if x is an input then g(x) = f(x);

(ii) if x is an AND gate then g(x) = 1 iff g(y) = 1 for every predecessor y of x;

(iii) if x is an OR gate then g(x) = 1 iff g(y) = 1 for some predecessor y of x;

(iv) if x is a NOT gate then g(x) = 1 iff g(y) = 0 for the unique predecessor y of x.

We say that the circuit C computes the function ϕ : {0, 1}^{I} → {0, 1}^{O}, where O is the set of output vertices, if ϕ(f) = g|_{O} for the function g just defined.

A circuit is binary if the in-degree of every vertex is at most 2. It is monotone if there are no NOT gates. It is easy to prove that if C is a monotone circuit then the function ϕ it computes is montotone, in the sense that if f ≤ g (i.e. f(x) < g(x) for all x) then ϕ(f) ≤ ϕ(g).

Proposition 33. There is a function ϕ : {0, 1}^{n} → {0, 1} that cannot be computed by a binary circuit of size less than \frac{2^{n}}{100n}.

Proof. The number of binary circuits with m vertices is at most (10m^{2})^{m}. For these to compute all functions from {0, 1}^{n} to {0, 1}, we need (10m^{2})^{m} ≥ 2^{2^{n}} which implies m(2 log_{2} m + log_{2} 10) ≥ 2^{n}, giving m ≥ \frac{2^{n}}{100n}.

Given a circuit C, let us label the input vertices x_{1}, x_{2}, …, x_{n} and the remaining vertices x_{n+1}, x_{n+2}, …, x_{m} in such a way that each x_{i} comes after its predecessors in the circuit. For each i, let

A_{i} = {f : {x_{1}, x_{2}, …, x_{n}} → {0, 1} : g(x_{i}) = 1 for g as defined earlier}.

Then for 1 ≤ i ≤ n, A_{i} = {f : f(x_{i}) = 1} = E_{i} (where E stands for “elementary”). We can think of E_{i} as a subset of {0, 1}^{n}—consisting of all points with i-coordinate 1.

If x_{i} is an AND (OR) gate with predecessors x_{j} and x_{k} then A_{i} = A_{j} ∩A_{k} (A_{j} ∪ A_{k}). If x_{i} is a NOT gate with predecessor x_{j} then A_{i} = A_{j}^{c}. Hence ϕ : {0, 1}^{n} → {0, 1} can be computed by a circuit C of size m iff there is a sequence A_{1}, A_{2}, …, A_{m} of sets with the following properties:

(i) if 1 ≤ i ≤ n then A_{i} = E_{i} = {f : f(i) = 1};

(ii) if i > n then A_{i} = A_{j} ∩ A_{k}, A_{i} = A_{j} ∪ A_{k} or A_{i} = A_{j}^{c} for some j, k < i;

(iii) A_{m} = A(ϕ) = {f : ϕ(f) = 1}.

Razborov’s method of approximations

The basic idea of the proof to follow, that a certain monotone function ϕ has high monotone circuit complexity, is this:

We shall define a lattice L of subsets of {0, 1}^{n} with operations ⊓ and ⊔ that approximate ∩ and ∪ well enough that whenever we take a sequence A_{1}, A_{2}, …, A_{m} as above and define a new sequence B_{1}, B_{2}, …, B_{m} by using ⊓ and ⊔ instead of ∩ and ∪ then B_{m} is close to A_{m} (if m is small). It follows that every function with small monotone circuit complexity is approximated by some function in L. We then need to show that {f : ϕ(f) = 1} is not approximated by a function in L.

Notation. If B, B′ ∈ L, define δ_{⊔}(B, B′) to be B⊔B′−(B∪B′) and δ_{⊓}(B, B′) to be B ∩ B′ − (B ⊓ B′).

Let L be a lattice of subsets of {0, 1}^{n} with operations ⊓ and ⊔ and suppose that the elementary sets E_{i} = {ε ∈ {0, 1}^{n} : ε_{i} = 1} are contained in L. Suppose that A ⊔ B ⊃ A ∪ B and A ⊓ B ⊂ A ∩ B for every A, B ∈ L.

Now let us suppose that A_{1}, A_{2}, …, A_{m} is a monotone straight-line calculation of A_{m} = A, i.e. A_{i} = E_{i} if i ≤ n, and A_{i} = A_{j} ∪A_{k} or A_{i} = A_{j} ∩A_{k} for some j, k < i if i > n. Let B_{1}, B_{2}, …, B_{m} be defined by B_{i} = A_{i} if i ≤ n, and B_{i} = B_{j} ⊔ B_{k} or B_{i} = B_{j} ⊓ B_{k} according as A_{i} = A_{j} ∪ A_{k} or A_{i} = A_{j} ∩ A_{k} for i > n. Write M_{i}, N_{i} for the two sets that make B_{i}.

Lemma 34. Under these circumstances,

B_{m} ⊂ A_{m} ∪ ⋃_{i=1}^{m} δ_{⊔}(M_{i}, N_{i})

and

B_{m} ⊃ A_{m} − ( ⋃_{i=1}^{m} δ_{⊓}(M_{i}, N_{i})).

Proof. The proof is by induction on m.

If B_{m} = B_{j} ⊔ B_{k} then

B_{m} = B_{j} ∪ B_{k} ∪ δ_{⊔}(B_{j}, B_{k})
⊂ A_{j} ∪ ⋃_{i=1}^{j} δ_{⊔}(M_{i}, N_{i}) ∪ A_{k} ∪ ⋃_{i=1}^{k} δ_{⊔}(M_{i}, N_{i}) ∪ δ_{⊔}(M_{m}, N_{m})

⊂ A_{m} ∪ ⋃_{i=1}^{m} δ_{⊔}(M_{i}, N_{i})

(as A_{j} ∪ A_{k} = A_{m}) and

B_{m} ⊃ B_{j} ∪ B_{k}
⊃ (A_{j} − ( ⋃_{i=1}^{j} δ_{⊓}(M_{i}, N_{i}))) ∪ (A_{k} − ( ⋃_{i=1}^{k} δ_{⊓}(M_{i}, N_{i})))

⊃ A_{m} − ( ⋃_{i=1}^{m} δ_{⊓}(M_{i}, N_{i})).

Similarly, if B_{m} = B_{j} ⊓ B_{k} then

B_{m} = B_{j} ∩ B_{k} − δ_{⊓}(B_{j}, B_{k})
⊃ (A_{j} − ( ⋃_{i=1}^{j} δ_{⊓}(M_{i}, N_{i}))) ∩ (A_{k} − ( ⋃_{i=1}^{k} δ_{⊓}(M_{i}, N_{i}))) − δ_{⊓}(B_{j}, B_{k})

⊃ A_{m} − ( ⋃_{i=1}^{m} δ_{⊓}(M_{i}, N_{i}))

and

B_{m} ⊂ B_{j} ∩ B_{k}
⊂ (A_{j} ∪ ⋃_{i=1}^{j} δ_{⊔}(M_{i}, N_{i})) ∩ (A_{k} ∪ ⋃_{i=1}^{k} δ_{⊔}(M_{i}, N_{i}))

⊂ A_{m} ∪ ⋃_{i=1}^{m} δ_{⊔}(M_{i}, N_{i}).

Definition of L

Let W, W_{1}, W_{2}, …, W_{r} be sets. We shall say that W_{1}, W_{2}, …, W_{r} entail W, and write W_{1}, W_{2}, …, W_{r} ⊢ W if W_{i} ∩ W_{j} ⊂ W for all i ≠ j. (The sets W_{1}, W_{2}, …, W_{r} are not necessarily distinct.)

Write [n]^{(≤k)} for the set of all subsets of {1, 2, …, n} of size at most k. Say that a subset A ⊂ [n]^{(≤k)} is closed if whenever W_{1}, W_{2}, …, W_{r} ∈ A and W_{1}, W_{2}, …, W_{r} ⊢ W then W ∈ A (where r ≥ 2 is some fixed number to be chosen later). If A ⊂ [n]^{(≤k)} then the closure of A, written A^{∗}, is the intersection of all closed sets that contain A.

Given a set A ⊂ [n]^{(≤k)}, write ⌈A⌉ for the set of all graphs with vertex set [n] that contain a clique with vertex set A for some A ∈ A.

The lattice L will consist of all sets of the form ⌈A⌉ for A closed. We define the operations ⊔ and ⊓ by ⌈A⌉⊓⌈B⌉ = ⌈A∩B⌉ and ⌈A⌉⊔⌈B⌉ = ⌈(A∪B)^{∗}⌉. It is easy to check that ⌈A⌉ ⊓ ⌈B⌉ ⊂ ⌈A⌉ ∩ ⌈B⌉ and ⌈A⌉ ⊔ ⌈B⌉ ⊃ ⌈A⌉ ∪ ⌈B⌉.

Lemma 35. A closed set can have at most (r − 1)^{k} minimal elements.

Proof. If A is closed and A_{1}, A_{2}, …, A_{r}, A are minimal elements of A then it is not possible to find B ⊊ A such that A_{i} ∩ A_{j} ⊂ B for all i ≠ j. We shall show that any collection of sets with this property has cardinality at most (r − 1)^{k}. We do this by induction on r (noting that the result is clear when r = 2).

Let M be a collection of sets with this property and let F ∈ M. For each C ⊂ F, let M_{C} = {A ∈ M : A ∩ F = C}. If A_{1}, A_{2}, …, A_{r−1}, A ∈ M_{C} and if B ⊊ A with A_{i} ∩ A_{j} ⊂ B for all i ≠ j, then C ⊂ B, from which it follows that A_{1}, A_{2}, …, A_{r−1}, F ⊢ B, a contradiction. It follows that the sets A − F = A − C for A ∈ M_{C} have the same property, but with k and r replaced by k − |C| and r − 1.

Hence by induction, |M_{C}| ≤ (r − 2)^{k−|C|} and so

|M| ≤ ∑_{C⊂F}(r−2)^{k−|C|} ≤ ∑_{i=0}^{|F |} \binom{|F |}{i}(r−2)^{k−i} ≤ ∑_{i=0}^{k} \binom{k}{i}(r−2)^{k−i} = (r−1)^{k}.

Example. Let B_{1}, B_{2}, …, B_{k} be disjoint sets of size r−1 and let M ⊂ [n]^{(≤k)} be the collection {A : |A ∩ B_{i}| = 1, 1 ≤ i ≤ k}. Then |M| = (r − 1)^{k}. If A_{1}, A_{2}, …, A_{r} ∈ M then for all i, there exist j ≠ k with A_{j} ∩ B_{i} = A_{k} ∩ B_{i}. Therefore if A_{1}, A_{2}, …, A_{r} ⊢ B we have |B ∩ B_{i}| ≥ 1 for all i.

Definition. A g-colouring of [n] is a function f : [n] → [g]. If A ⊂ [n] then we say A is properly coloured (or PC ) if every element of A has a different colour (i.e. f|_{A} is an injection).

Lemma 36. Let A ⊂ [n]^{(≤k)} be a set system and let A ∈ [n]^{(≤k)} be such that A_{1}, A_{2}, …, A_{r} ⊢ A for some A_{1}, A_{2}, …, A_{r} ∈ A. Let f : [n] → [g] be a random g-colouring of [n]. Then the probability that A is properly coloured and no A′ ∈ A is PC is at most (1 − \frac{g(g−1)...(g−k+1)}{g^{k}})^{r}.

Proof. The probability in question is clearly at most

ℙ[A is PC and no A_{i} is PC for i = 1, 2, …, r]
≤ ℙ[no A_{i} is PC|A is PC]
= ∏_{i=1}^{r} ℙ[A_{i} is not PC|A is PC]  (since the A_{i} − A are disjoint)

= ∏_{i=1}^{r} (1 − ℙ[A_{i} is PC|A is PC]) .

But ℙ[A_{i} is PC|A is PC] ≥ \frac{g(g−1)...(g−k+1)}{g^{k}} which proves the lemma.

Lemma 37. Let A ⊂ [n]^{(≤k)} be a set system and let f : [n] → [g] be a random g-colouring of [n]. Then the probability that no A′ ∈ A is PC but some A ∈ A^{∗} is PC is at most n^{k} (1 − \frac{g(g−1)...(g−k+1)}{g^{k}})^{r}.

Proof. Enumerate the sets in A^{∗} as A_{1}, A_{2}, …, A_{m}, starting with the sets in A, such that each A_{i} ∈ A^{∗} − A is entailed by r earlier sets. Then the event in question is the disjoint union of the events ‘A_{i} is the first set to be PC’ for i > |A|. By Lemma 36, the probability of this is at most (1 − \frac{g(g−1)...(g−k+1)}{g^{k}})^{r}. But obviously m ≤ ∑_{i=0}^{k} \binom{n}{i} ≤ n^{k} and so the lemma is proved.

A g-colouring f defines a complete g-partite graph G(f) in [n] where you join x to y iff f(x) ≠ f(y). A set A is PC iff the clique with vertex set A is a subgraph of G(f). So if A is a set system, then G(f) ∈ ⌈A⌉ iff some A ∈ A is PC. So Lemma 37 gives an upper bound on the proportion of complete g-partite graphs contained in a set of the form ⌈A^{∗}⌉ − ⌈A⌉.

The main argument

Let C be the set of all graphs on n vertices that contain a clique of size m (so C can be thought of as a subset of {0, 1}^{[n]^{(2)}}). Suppose that A_{1}, A_{2}, …, A_{N} = C is a monotone straight-line computation of C and let B_{1}, B_{2}, …, B_{N} be the results of the corresponding computation in L with ∩ and ∪ replaced by ⊓ and ⊔ respectively.

Case 1: B_{N} is the set of all graphs on [n]. We know by Lemma 34 that B_{N} ⊂ A_{N} ∪ ⋃_{l=1}^{N} δ_{⊔}(M_{l}, N_{l}) where (M_{l}, N_{l}) is a pair of the form (B_{i}, B_{j}). But

δ_{⊔}(B_{i}, B_{j}) = ⌈(B_{i} ∪ B_{j})^{∗}⌉ − ⌈B_{i} ∪ B_{j}⌉ = ⌈(B_{i} ∪ B_{j})^{∗}⌉ − (⌈B_{i}⌉ ∪ ⌈B_{j}⌉) .

By Lemma 37, the proportion of complete (m−1)-partite graphs in δ_{⊔}(B_{i}, B_{j}) is therefore at most n^{k} (1 − \frac{(m−1)(m−2)...(m−k)}{(m−1)^{k}})^{r}. Set k = \sqrt{m}. Then

\frac{(m − 1)(m − 2) … (m − k)}{(m − 1)^{k}} ≥ (1 − \frac{k}{m})^{k} ≈ e^{− \frac{k^{2}}{m}} = \frac{1}{e} = c.

So the proportion of complete (m − 1)-partite graphs in δ_{⊔}(B_{i}, B_{j}) is at most n^{k}e^{−cr}, which implies that N ≥ e^{cr−k log n}. So we will need cr ≥ 2k log n.

Case 2: B_{N} is not the set of all graphs. First we attain an upper bound on the number of m-cliques contained in B_{N}. We know that B_{N} is a set of the form ⌈A⌉ for some closed set A. Any m-clique in ⌈A⌉ must have a vertex set of size m that contains some minimal element A of A as a subset, with |A| ≥ 2.

Now by Lemma 35, the number of minimal elements of A of size i is at most (r − 1)^{i}. Each is contained in at most \binom{n−i}{m−i} sets of size m, so the number of m-cliques in ⌈A⌉ is at most

∑_{i=2}^{k}(r − 1)^{i}\binom{n − i}{m − i} ≤ \binom{n}{m} ∑_{i=2}^{k}(r − 1)^{i} (\frac{m}{n})^{i}

so if \frac{(r−1)m}{n} ≤ \frac{1}{2} then this is at most \frac{1}{2} \binom{n}{m}.

It remains to obtain an upper bound for the number of m-cliques in any δ_{⊓}(⌈A⌉, ⌈B⌉) with A, B closed. Then we will be done by Lemma 34 since A_{N} ⊂ B_{N} ∪_{i=1}^{N} δ_{⊓}(M_{i}, N_{i}) and so very many steps will be required to reach \frac{1}{2} \binom{n}{m}.

Suppose that K(Z) is an m-clique with vertex set Z, and suppose that K(Z) ∈ (⌈A⌉ ∩ ⌈B⌉) − (⌈A ∩ B⌉). Then Z must contain minimal elements X and Y of A and B respectively, and X ∪ Y is not an element of A ∩ B. The only way this can happen is if |X ∪Y | > k, so either |X| > \frac{k}{2} or |Y | > \frac{k}{2}. It follows that the number of possible Z is at most

2 ∑_{i> \frac{k}{2}}(r − 1)^{i}\binom{n − i}{m − i} ≤ 2\binom{n}{m} ∑_{i> \frac{k}{2}} (\frac{(r − 1)m}{n})^{i} ≤ 4\binom{n}{m}2^{− \frac{k}{2}} .

It follows that, in case 2, N ≥ \frac{\frac{1}{2} \binom{n}{m}}{4\binom{n}{m}2^{− \frac{k}{2}}} = \frac{1}{8}2^{\frac{k}{2}} .

We have shown that N ≥ min\{e^{\frac{cr}{2}} , \frac{1}{8}2^{\frac{k}{2}} \}, subject to the restrictions k^{2} = m, r ≥ ck log n and rm ≤ cn, so r ≥ c\sqrt{m} log n, and so m^{\frac{3}{2}} log n ≤ cn,

and so m ≤ (\frac{cn}{log n})^{\frac{2}{3}} . So take that for m, and let k = (\frac{cn}{log n})^{\frac{1}{3}} and

r = ck log n; we obtain a bound of e^{(^{\frac{cn}{log n}})}^{\frac{1}{3}} as the monotone circuit complexity of a function of \binom{n}{2} variables.

6 Algebraic methods

Theorem 38 (Frankl, Wilson). Let F be a subset of [n]^{(k)}—i.e. a set system consisting of subsets of [n] of size k. Let p be a prime and let λ_{1}, λ_{2}, …, λ_{s} be residues mod p, none of them congruent to k. Let Λ be the set {λ_{1}, λ_{2}, …, λ_{s}}

Suppose that |F ∩ F′| is congruent to some λ ∈ Λ whenever F, F′ ∈ F with F ≠ F′. Then |F| ≤ \binom{n}{s}.

Proof. Assume wlog s < k. For each i < j let N(i, j) be the \binom{n}{i} × \binom{n}{j} matrix defined on pairs (A, B) ∈ [n]^{(i)} × [n]^{(j)} by

N(i, j)(A, B) = \{ \begin{matrix}1 & if A ⊂ B \\ 0 & if A ⊄ B \end{matrix} .

Let V be the vector space over ℝ spanned by the rows of N(s, k). There are \binom{n}{s} rows, so dim V ≤ \binom{n}{s}.

Let i ≤ s and look at the matrix N(i, s)N(s, k), which is an \binom{n}{i} × \binom{n}{k} matrix defined on pairs (A, B) ⊂ [n]^{(i)} × [n]^{(k)}. We see that

N(i, s)N(s, k)(A, B) = ∑_{C⊂[n]^{(s)}} 1_{A⊂C}1_{C⊂B}

= \{ \begin{matrix}\binom{k−i}{s−i} & if A ⊂ B \\ 0 & if A ⊄ B \end{matrix}

so N(i, s)N(s, k)(A, B) = \binom{k−i}{s−i}N(i, k)(A, B). It follows that the rows of N(i, k) belong to V.

Now let M(i, k) = N(i, k)^{T} N(i, k). If (A, B) ∈ [n]^{(k)} × [n]^{(k)}, then

M(i, k)(A, B) = ∑_{C⊂[n]^{(i)}} 1_{C⊂A}1_{C⊂B} = \binom{|A ∩ B|}{i}.

Now choose a_{1}, a_{2}, …, a_{s} such that ∏_{λ∈Λ}(x − λ) = ∑_{i=1}^{s} a_{i}\binom{x}{i} and let M = ∑_{i=1}^{s} a_{i}M(i, k). The rows of M(i, k) and hence M belong to V. But M(A, B) ≡ 0 (mod p) if A, B ∈ F with A ≠ B since then A ∩ B ≡ λ (mod p) for some λ ∈ Λ and so ∑ a_{i}\binom{|A∩B|}{i} ≡ 0 (mod p) (by definition of a_{1}, …, a_{s}). If A = B then |A ∩ B| ≢ λ (mod p) for any λ ∈ Λ so M(A, B) ≢ 0 (mod p). That applies if A, B ∈ F. So the restriction of M to pairs (A, B) ∈ F has rows which are linearly independent over the field 𝔽_{p} and hence over ℝ, and so is a matrix of rank |F|. But since the rows of M belong to V, M has rank at most \binom{n}{s}. So |F| ≤ \binom{n}{s}.

Borsuk’s conjecture

Borsuk asked whether every convex body in ℝ^{d} can be partitioned into at most d + 1 sets of smaller diameter.

Larman had the following idea for potential counterexamples. Take a set system F ⊂ [n]^{(k)} and associate with F ∈ F a 01-sequence in the usual way and regard it as a point in ℝ^{n}. Then writing F for this point as well, we have d(F, F′) = |F ΔF′|^{\frac{1}{2}} . In particular, this distance is maximized when |F ∩ F′| is minimized. So look for a set system F such that however you partition it into F_{1} ∪ F_{2} ∪ ⋯ ∪ F_{m} if m is not too large then some F_{i} contains F and F′ with |F ∩ F′| minimal (amongst all pairs from F).

Corollary 39. Let p be a prime and let n = 4p. Let F ⊂ [n]^{(2p)} be such that for all F, F′ ∈ F, |F ∩ F′| ≠ p. Then |F| ≤ \binom{n}{p−1}.

Proof. The condition implies that |F ∩ F′| ∈ {1, 2, …, p − 1} (mod p) if F ≠ F′.

Disproof of Borsuk’s conjecture

Let m = 4p and let n = \binom{m}{2}. Identify [m]^{(2)} with [n].

Given any partition of [m] into two sets A and B of equal size, let G(A, B) be the complete bipartite graph with vertex sets A and B. Then, if (A, B) and (C, D) are two such partitions with |A ∩ C| = k, we have |G(A, B) ∩ G(C, D)| = k^{2} + (2p − k)^{2} which is minimized when k = p. So by Corollary 39, any subset F′ ⊂ F that does not contain a pair G(A, B) and G(C, D) at maximal distance apart has size at most \binom{m}{p−1} (since if you look at the A’s you get A ⊂ [m]^{(2p)} with A ≠ A′ ⟹ |A ∩ A′| ≠ p). But |F| = \frac{1}{2} \binom{m}{2p}. So the smallest partition has size at least \binom{m}{2p}/2\binom{m}{p−1}.

Now, \binom{4p}{2p}/\binom{4p}{p−1} is ‘roughly’ 2^{4p}/ (\frac{4}{3})^{3p} · 4^{p} = α^{4p} for some α > 1. Hence we have shown the following:

Theorem 40. There is a convex body in ℝ^{n} that cannot be partitioned into c^{\sqrt{n}} parts of smaller diamter, with c > 1 an absolute constant.

Theorem 41. Let p be a prime and n a positive integer. Let G be a graph with vertex set [n]^{(p^{2}−1)} where F is joined to F′ iff |F ∩ F′| ≡ −1 (mod p). Then G contains no clique or independent set of size greater than \binom{n}{p−1}.

Proof. If F is an independent set then |F ∩ F′| ∈ {0, 1, …, p − 2} (mod p) if F ≠ F′, so by Theorem 38, F ≤ \binom{n}{p−1}. If F is a clique then for F ≠ F′ we have |F ∩ F′| ∈ {p − 1, 2p − 1, …, p^{2} − p − 1} which implies by Theorem 38 with respect to some prime q > p − 1, that |F| ≤ \binom{n}{p−1}.

If we now set n = p^{3}, we find that the Ramsey number R (\binom{p^{3}}{p−1} + 1) is

greater than \binom{p^{3}}{p^{2}−1}. Let k = \binom{p^{3}}{p−1} ≤ p^{3p}. Then

\binom{p^{3}}{p^{2} − 1} ≥ p^{p^{2}−1} ≥ (\frac{log k}{log log k} )^{c(\frac{log k}{log log k})^{2}} ≥ e^{c log log k(\frac{log k}{log log k})^{2}} = e^{c \frac{(log k)^{2}}{log log k}}

which exceeds any fixed power of k.

Theorem 42. There is a subset A ⊂ \{1, 2, …, n\} of size c\sqrt{n} containing no quadruple (x, y, z, w) with x + y = z + w except degenerate ones.

Proof. Let p be an odd prime. Let Γ ⊂ [p]^{2} be the set

Γ = {(x, x^{2} (mod p)) : x = 1, 2, …, p}.

Then

(x, x^{2})+(y, y^{2}) = (z, z^{2})+(w, w^{2}) (mod p) ⟹ \{ \begin{matrix}x − z ≡ w − y & (1) \\ x^{2} − z^{2} ≡ w^{2} − y^{2} & (2) \end{matrix} .

If x ≠ z then x ≢ z and we can divide (2) by (1) to get x + z ≡ w + y, giving x ≡ w and y ≡ z, and so x = w and y = z.

Now map Γ to [n] by the map (a, b) ↦ a+2pb−2p. If a_{i}, b_{i}, c_{i}, d_{i} ∈ [p] with a_{1} + 2pa_{2} + b_{1} + 2pb_{2} = c_{1} + 2pc_{2} + d_{1} + 2pd_{2} then a_{1} + b_{1} ≡ c_{1} + d_{1} (mod 2p) from which it follows that a_{1} + b_{1} = c_{1} + d_{1} and so a_{2} + b_{2} = c_{2} + d_{2}. So the image of Γ is a subset of [2p^{2}] of size p containing no non-trivial x + y = z + w.

Theorem 43. For all n ∈ ℕ, there is a family A ⊂ ℙ[2n] of size 2^{n} with no non-trivial solutions of AΔB = CΔD.

Proof. We can identify ℙ[2n] in the usual way with {0, 1}^{2n} and we can identify that with {0, 1}^{n} × {0, 1}^{n}. Now we’d like to find X ⊂ {0, 1}^{2n} with no non-trivial solutions to x + y = z + w.

We can think of {0, 1}^{n} as the additive group of the field with 2^{n} elements, and then let X = {(x, x^{3}) : x ∈ {0, 1}^{n}} ⊂ {0, 1}^{n} × {0, 1}^{n}. As before, if (x, x^{3}) + (y, y^{3}) = (z, z^{3}) + (w, w^{3}) then x + y = z + w and x^{3} + y^{3} = z^{3} + w^{3} which implies, unless x = y and z = w, that x^{2} + xy + y^{2} = z^{2} + zw + w^{2}. But (x + y)^{2} = x^{2} + y^{2} = z^{2} + w^{2} so xy = zw. That is enough to show that (x, y) = (z, w).

Theorem 44 (Behrend, 1947). There is a subset X ⊂ [n] of size ne^{−c\sqrt{log n}} that contains no arithmetic progression of length 3.

Proof. Let m, k ∈ ℕ and define B_{r} ⊂ [m]^{k} to be the set

B_{r} = {(x_{1}, x_{2}, …, x_{k}) : ∑_{i=1}^{k} x_{i}^{2} = r}.

This set lies on the surface of a sphere so contains no three collinear points, and in particular no arithmetic progression of length 3 (in the obvious sense). There are at most km^{2} values of r for which B_{r} ≠ ∅, so some B_{r} has size at least \frac{m^{k}}{m^{2}k}. Let B be such a B_{r}. Now map B to [(2m)^{k}] by the map ϕ(x_{1}, x_{2}, …, x_{k}) = x_{1} + 2mx_{2} + (2m)^{2}x_{3} + ⋯ + (2m)^{k−1}x_{k}. Then if ϕ(x), ϕ(y) and ϕ(z) are in arithmetic progression, we have x_{1}, y_{1}, z_{1} in arithmetic progression mod 2m, giving x_{1}, y_{1}, z_{1} in arithmetic progression. Then 2mx_{2}, 2my_{2}, 2mz_{2} are in arithmetic progression mod (2m)^{2} giving x_{2}, y_{2}, z_{2} in arithmetic progression and so on. So x, y, z are in arithmetic progression, a contradiction.

Let n = (2m)^{k}. Then we have found a subset of [n] with no arithmetic progression of length 3 with size at least \frac{m^{k}}{m^{2}k}. Let k = \sqrt{log n} and m = \frac{1}{2}e^{\sqrt{log n}}. Then the size is at least

\frac{n}{2^{\sqrt{log n}} \frac{1}{4}e^{2\sqrt{log n}}\sqrt{log n}} ≥ ne^{−c\sqrt{log n}}.

7 Topological methods

Theorem 45 (The Borsuk-Ulam Theorem). Let

S_{n} = {x ∈ ℝ^{n+1} : ∥x∥ = 1}.

Let f : S_{n} → ℝ^{n} be any continuous function. Then there exists x ∈ S_{n} such that f(x) = f(−x).

Corollary 46. Let A_{1}, A_{2}, …, A_{n+1} be subsets of S_{n}, all either open or closed, such that S_{n} = ⋃_{i=1}^{n+1} A_{i}. Then some A_{i} contains a pair {x, −x} of antipodal points.

Proof. 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 the Borsuk-Ulam Theorem, we can find x such that f(x) = f(−x). We know that x ∈ A_{i} for some i.

If i ≤ n and A_{i} is closed then d(−x, A_{i}) = 0 so −x ∈ A_{i}.

If i ≤ n and A_{i} is open then d(−x, A_{i}) = 0. Then a small perturbation −y of −x is in A_{i}, and y ∈ A_{i} since A_{i} is open and the perturbation small.

This shows that we are done if either x ∈ A_{i} for some i ≤ n or −x ∈ A_{i} for some i ≤ n. So we can assume that this is not the case. Then x ∈ A_{n+1} and −x ∈ A_{n+1}.

Theorem 47. For every n there is a finite triangle-free graph with chromatic number n.

Proof. First, we will find an infinite graph G. Let V (G) = S_{n} and join x to y iff ⟨x, y⟩ < −\frac{1}{2}—i.e. the angle between x and y is greater than 120^{∘}. Clearly G is triangle-free. Now, let S_{n} = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n+1}. Then, by Corollary 46, some Ā_{i} contains an antipodal pair {x, −x}. Choose y and z in A_{i}, close enough to x and −x for ⟨y, z⟩ < −\frac{1}{2}, and then we have an edge inside A_{i}. So χ(G) > n + 1.

To make this into a finite graph, let δ > 0 be small and let Δ be a δ-net of S_{n}—i.e. for all x ∈ S_{n}, there is some y ∈ Δ such that d(x, y) < δ. Join x, y ∈ Δ iff ⟨x, y⟩ < −\frac{2}{3}. Now let Δ = B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{n+1}. Let A_{i} ⊂ S_{n} be {x : ∃y ∈ B_{i} with d(x, y) < δ}. Then some Ā_{i} contains an antipodal pair \{z, −z\}. But we can find v, w ∈ B_{i} close to z, −z, so ⟨v, w⟩ < −\frac{2}{3} and so the colouring is not proper.

Theorem 48 (Kneser’s conjecture, proved by Lovasz). Let G be the graph with vertex set [n]^{(k)} in which A and B are joined iff A ∩ B = ∅. Then χ(G) = max{n − 2k + 2, 1}.

Proof (due to Greene). First consider the colouring

ϕ(G) = min{min A, n − 2k + 2}.

This is an (n − 2k + 2)-colouring. If ϕ(A) = ϕ(B) < n − 2k + 2 then min A = min B and so A ∩ B ≠ ∅. If ϕ(A) = ϕ(B) = n − 2k + 2 then A, B ⊂ [n − 2k + 2, n], but this set has size 2k − 1 and so A and B cannot be disjoint.

To show that χ(G) = n − 2k + 2, let d = n − 2k + 1 and let X ⊂ S_{d} be a set of n points in general position, so no d + 1 points of X are contained in a d-dimensional subspace of ℝ^{d+1}. Identify [n] with X, or, in other words, take V (G) = X^{(k)}.

Let ϕ : X^{(k)} → [d] be a colouring of X^{(k)}. For each x ∈ S_{d}, let H_{x} = {y ∈ S_{d} : ⟨x, y⟩ > 0}. For each i ≤ d, let A_{i} be the set of all points x ∈ S_{d} such that H_{x} contains a k-tuple from X coloured with colour i. Let A_{d+1} = S_{d} − (A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{d}). Note that A_{i} is open for i ≤ d, and so A_{d+1} is closed.

By the Borsuk-Ulam Theorem, some A_{i} must contain an antipodal pair {x, −x}. If i ≤ d, then both H_{x} and H_{−x} contain k-tuples coloured with colour i. But H_{x} and H_{−x} are disjoint, so these k-tuples are disjoint and the colouring is not proper.

If i = d + 1 then neither H_{x} nor H_{−x} contains any k-tuple from X. Hence S_{d} − (H_{x} ∪ H_{−x}) = {y : ⟨x, y⟩ = 0} contains at least n − 2(k − 1) = d + 1 points, contradicting the fact that the points of X are in general position.

Next, we look at another equivalent formulation of the Borsuk-Ulam Theorem.

Theorem 49. Let B_{n} = {x ∈ ℝ^{n} : ∥x∥ ≤ 1}. Then there is no continuous map f : B_{n} → S_{n−1} that is antipodal on the boundary—i.e. such that f(x) = −f(−x) for every x ∈ S_{n−1}.

Before proving this, we observe that it implies the Borsuk-Ulam Theorem.

Proof (of Theorem 45). Suppose that we could find some continuous map f : S_{n} → ℝ^{n} that did not identify two antipodal points. Then we can define g : S_{n} → ℝ^{n} by g(x) = (f(x) − f(−x))/∥f(x) − f(−x)∥. Note that g is continuous and g(−x) = −g(x). Also, the image of g lies inside S_{n−1}.

Now define h : B_{n} → S_{n−1} by h(x) = g((x, \sqrt{1 − ∥x∥^{2}})). Then h is continuous, and antipodal on the boundary of B_{n}.

Exercise. Show that Theorem 45 implies Theorem 49.

Theorem 50 (Tucker’s Lemma). Let T be a triangulation of B_{n} that is antipodally symmetric on the boundary. That is, if σ ∈ T with σ ⊂ S_{n−1} then −σ ∈ T. Let λ be a labelling of the vertices of T with labels from the set {1, 2, …, n} ∪ {−1, −2, …, −n}. Then if this labelling satisfies λ(−x) = −λ(x) for every vertex x, there must be some edge (i.e. 1-simplex) with vertices labelled i and −i.

We shall prove Tucker’s lemma in an alternative formulation. Let L be the “octahedral triangulation” consisting of all convex hulls of up to n of the vectors ±e_{i} (where (e_{i})_{i=1}^{n} is the standard basis of ℝ^{n}) such that you never use both e_{i} and −e_{i}.

Then a simplicial map from T to L is exactly a map ϕ that takes the vertices of T to {e_{1}, e_{2}, …, e_{n}} ∪ {−e_{1}, −e_{2}, …, −e_{n}} such that if x and y are vertices of the same simplex in T then {ϕ(x), ϕ(y)} ≠ {e_{i}, −e_{i}} for any i.

So under the hypotheses on T, Tucker’s lemma says that there is no simplicial map ϕ : T → L such that ϕ|_{S_{n−1}} is antipodal.

We first show that Tucker’s lemma implies Theorem 49.

Proof (of Theorem 49). Assume Theorem 49 is false and let f : B_{n} → S_{n−1} be a continous map, antipodal on the boundary. We shall construct a counterexample to Tucker’s lemma.

Since f is uniformly continuous, we can find δ > 0 such that whenever d(x, y) < δ we have d(f(x), f(y)) < \frac{1}{\sqrt{n}}. Let T be a triangulation of B_{n} of mesh less than δ (i.e. with every simplex having diameter less than δ). We now define a simplicial map ϕ : T → L as follows. For each vertex x ∈ T, let ϕ(x) be the nearest point of {±e_{1}, ±e_{2}, …, ±e_{n}} to f(x), choosing i minimal in the case of a tie. Note that ϕ(−x) = −ϕ(x) for x ∈ S_{n−1}. Also,

ϕ(x) = \left\{{e_{i} \atop −e_{i}}\right\} ⟹ f(x)_{i} \{{≥ \frac{1}{\sqrt{n}} \atop ≤ −\frac{1}{\sqrt{n}}}

so if x and y belong to the same simplex then {ϕ(x), ϕ(y)} ≠ {e_{i}, −e_{i}} by choice of δ.

Given a simplicial complex T, a k-chain is a set of k-simplices belonging to T. We shall think of these sets as formal sums of simplices over ℤ_{2}. Given a simplex σ, the boundary ∂σ is the set of all (k − 1)-facets of σ. Given a k-chain σ_{1} + σ_{2} + ⋯ + σ_{r} = A, we define ∂A to be ∂σ_{1} + ∂σ_{2} + ⋯ + ∂σ_{r}. We have the following simple facts: ∂(A + A′) = ∂A + ∂A′ and ∂∂A = 0 (since this is true for a k-simplex σ). Given a simplicial map ϕ : T → K and a k-simplex σ ∈ T, we define ϕ_{k}(σ) to be ϕ(σ) if this is a k-simplex and 0 otherwise. If A = σ_{1} + σ_{2} + ⋯ + σ_{r} then ϕ_{k}(A) is defined to be ϕ_{k}(σ_{1}) + ϕ_{k}(σ_{2}) + ⋯ + ϕ_{k}(σ_{r}). It is easy to check (simplex by simplex) that ϕ_{k−1}(∂A) = ∂(ϕ_{k}(A)).

Proof (of Tucker’s lemma). This comes in three steps. Let T be a triangulation of B_{n}, let K be the restriction of T to S_{n−1}, assume that K is antipodally symmetric and let ϕ : T → L be a simplicial map. We also make the following extra assumption about T:

For 0 ≤ k ≤ n − 1, let

H_{k}^{+} = {x ∈ S_{n−1} : x_{k+2} = x_{k+3} = ⋯ = x_{n} = 0, x_{k+1} ≥ 0}.

and

H_{k}^{−} = {x ∈ S_{n−1} : x_{k+2} = x_{k+3} = ⋯ = x_{n} = 0, x_{k+1} ≤ 0}.

We shall assume that for each H_{k}^{±} there is a subcomplex of T that triangulates it.

Call such a triangulation proper and note that Tucker for proper triangulations still implies Theorem 49.

For each k, let A_{k}^{±} be the k-chain from T that triangulates H_{k}^{±} and let C_{k}^{±} = ϕ_{k}A_{k}^{±}. Let A_{k} be the k-chain from T that triangulates H_{k}^{+} ∪ H_{k}^{−} and let C_{k} = ϕ_{k}(A_{k}). Note in particular that A_{n−1} is simply the (n − 1)-chain of all (n − 1)-simplices in K. Let A_{n} be the chain of all n-simplices of T. We shall show the following facts:

(i) either C_{n−1} is 0 or it consists of all (n − 1)-simplices of L, i.e. either every (n − 1)-simplex of L has an odd number of preimages or every (n − 1)-simplex of L has an even number of preimages. We say that ϕ has odd or even degree respectively;

(ii) for any simplicial map from T to L, its restriction to A_{n−1} has even degree;

(iii) any antipodally symmetric map ϕ : K → L has odd degree.

The proofs of these facts are as follows:

(i) If this is false then there must be neighbouring (n − 1)-simplices σ, τ ∈ L with σ ∈ C_{n−1} and τ ∉ C_{n−1}. Then their common facet belongs to ∂C_{n−1}.

But ∂C_{n−1} = ϕ_{n−2}(∂A_{n−1}), and ∂A_{n−1} = 0, since any (n − 2)-simplex of K is a facet of exactly two (n − 1)-simplices. (ii) Let ϕ : T → L be a simplicial map. Then ϕ_{n−1}(A_{n−1}) = ϕ_{n−1}(∂A_{n}). But this is ∂(ϕ_{n}A_{n}) = 0 since ϕ_{n}A_{n} = 0, since L contains no n-simplices. (iii) Assume, for a contradiction, that ϕ has even degree, i.e. that C_{n−1} = 0. We know that A_{n−1} = A_{n−1}^{+} + A_{n−1}^{−}, so C_{n−1} = ϕ_{n−1}A_{n−1} = C_{n−1}^{+} + C_{n−1}^{−}. Since ϕ is antipodally symmetric and A_{n−1}^{+} is antipodal to A_{n−1}^{−}, C_{n−1}^{+} is antipodal to C_{n−1}^{−}, but also C_{n−1}^{−} = C_{n−1}^{+}, so C_{n−1}^{+} is antipodally symmetric. But C_{n−2} = ∂C_{n−1}^{+} so C_{n−2} is the boundary of an antipodally symmetric (n − 1)-chain.

Now assume, as an inductive hypothesis, that C_{k} is the boundary of an antipodally symmetric (k+1)-chain D_{k+1}. We can write D_{k+1} = E_{k+1}+E′_{k+1} with E_{k+1} antipodal to E′_{k+1} (from each pair σ, −σ in D_{k+1}, put one in E_{k+1} and the other in E′_{k+1}). Now C_{k} = C_{k}^{+} + C_{k}^{−} = ∂E_{k+1} + ∂E′_{k+1} and so C_{k}^{+} + ∂E_{k+1} = C_{k}^{−} + ∂E′_{k+1}, but C_{k}^{+} and C_{k}^{−} are antipodal, as are ∂E_{k+1} and ∂E′_{k+1}, so C_{k}^{+} + ∂E_{k+1} is antipodally symmetric. Also,

∂(C_{k}^{+} + ∂E_{k+1}) = ∂C_{k}^{+} + ∂∂E_{k+1} = C_{k−1} + 0.

Hence C_{0} is the boundary of a symmetric 1-chain which implies that it consists of an even number of pairs of antipodal points. But it is also ϕ_{0}A_{0} and so consists of exactly one pair of antipodal points, a contradiction.

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