The regularity lemma and applications - Higher-order Uniformity and Applications

Theorem 1.1 (Szemerédi). For all $𝜀 > 0$ , there exists $k = k (𝜀)$ such that the vertex set of any sufficiently large graph $G = (V, E)$ can be partitioned into $V_{1}, \dots, V_{s}$ , $s \leq k$ such that for all but an $𝜀$ -proportion of pairs $(V_{i}, V_{j})$ , $G (V_{i}, V_{j})$ is $𝜀$ -regular.

Remark.

$𝜀$ -regular means: looks like a “random” graph. We will define it more thoroughly at the end of the lecture.
In Theorem 1.1, it is also possible to ensure that all the $V_{i}$ are almost the same size.
$k$ is known to have a bad dependence on $𝜀$ : we have
$2^{2^{2^{. . . msup 2}}},$

where the tower of exponentials is of size $𝜀^{- C}$ .

Theorem 1.2 (Removal). For all $δ > 0$ , there exists $η > η (δ)$ such that the following holds. If $G$ is a graph on $n$ vertices with at most $η n^{3}$ triangles, then it is possible to remove $\leq δ n^{2}$ edges to make it triangle-free.

Sketch proof. Apply Theorem 1.1 with $𝜀 = \frac{δ}{4}$ to obtain $V_{1}, \dots, V_{s}$ , $s \leq k = k (δ)$ of almost equal size.

Remove all edges between $V_{i}$ and $V_{j}$ where $G (V_{i}, V_{j})$ fails to be $𝜀$ -regular, or where the density of $G (V_{i}, V_{j}) \leq 2 𝜀$ . The number of edges removed in this way is $\leq 𝜀 n^{2} + 2 𝜀 n^{2} < δ n^{2}$ .

Claim: The “reduced” graph is triangle-free.

Indeed, if $x, y, z$ form a triangle in $G^{'}$ , then $(x, y, z)$ must lie in $V_{i} \times V_{j} \times V_{k}$ with $G (V_{i}, V_{j})$ , $G (V_{i}, V_{k})$ , $G (V_{j}, V_{k})$ all regular and dense (density $\geq 2 𝜀$ ). Hence we in fact have $\geq 𝜀^{3} {(\frac{n}{k})}^{3} = \frac{δ^{3}}{2^{6}} \frac{n^{3}}{k (δ)}$ triangles in $G$ . This is a contradiction if $η < \frac{δ^{3}}{2^{6} k (δ)}$ . □

Theorem 1.3 (Corners). For all $α > 0$ , there exists $N_{0} = N_{0} (α)$ such that for all $N \geq N_{0}$ , the following holds. Let $A \subseteq {[N]}^{2}$ of density $α$ ( $| A | ∕ N^{2} = α$ ). Then $A$ contains a triple of the form $(x, y)$ , $(x + d, y)$ , $(x, y + d)$ with $d > 0$ .

Remark. The theorem as stated can be fairly easily deduced from a version where we only ask that $d \neq 0$ . To do this: note that if $A$ is symmetric, then existence of a triangle with $d < 0$ implies existence of one with $d > 0$ . Then one can “make $A$ symmetric” (in exchange for a loss in density) by intersecting $A$ with a reflection of $A$ through a suitably chosen point.

Proof. Let

\begin{array}{l} X & = {v_{u} = {(x, y) : x = u} : u \in [N]} \\ Y & = {h_{t} = {(x, y) : y = t} : t \in [N]} \\ Z & = {d_{s} = {(x, y) : x + y = s}} \end{array}

We define a tripartite graph on parts $X, Y, Z$ , where vertices are joined by an edge if and only if the intersection of the corresponding lines lies in $A$ . A triangle in this graph corresponds to three points

(u, t), (u, s - u), (s - t, t) \in A .

Setting $d = s - u - t$ , these points are $(u, t)$ , $(u, t + d)$ , $(u + d, t)$ .

If $A$ contains no corner with $d \neq 0$ , then the only triangles in this graph are the degenerate ones ( $d = 0$ ). There are $α N^{2} = | A |$ many of these, and they are edge disjoint. Pick $δ = \frac{α}{2}$ , then by triangle-removal, there exists $η = η (α)$ such that we can destroy $η N^{3}$ triangles by removing at most $δ N^{2}$ edges.

If $α N^{2} < η N^{3}$ , then should be able to remove all triangles. But this is a contradiction since all the triangles are edge disjoint. □

Theorem 1.4 (Roth). For all $α > 0$ , there exists $N_{0} = N_{0} (α)$ such that for all $N \geq N_{0}$ , every $A \subseteq [N]$ of density $α$ ( $= | A | ∕ N$ ) contains a non-trivial $3$ -AP (a triple $x, x + d, x + 2 d$ ).

Sketch proof. Let $B = {(x, y) \in {[N]}^{2} : x - y \in A}$ . By Theorem 1.3, $B$ contains $(x, y), (x, y + d), (x + d, y)$ with $d \neq 0$ . Then $x - y, x - (y + d) = x - y + d, x + d - y = x - y + d \in A$ . □

Proposition 1.5. Let $X, Y$ be sets, and $f : X \times Y \to [- 1, 1]$ . Then the following are equivalent:

(i) For any pair of sets $X^{'} \subseteq X$ , $Y^{'} \subseteq Y$ ,
$𝔼_{x \in X^{'}, y \in Y^{'}} f (x, y) \leq c_{1} \frac{| X |}{| X^{'} |} \frac{| Y |}{| Y^{'} |},$

where $𝔼_{x \in X} = \frac{1}{| X |} \sum_{x \in X}$ .

(ii) For any two functions

u : X \to [- 1, 1]

v : Y \to [- 1, 1]

| 𝔼_{x \in X, y \in Y} f (x, y) u (x) v (y) | \leq c_{2} .

(iii) $𝔼_{x, x^{'} \in X} 𝔼_{y, y^{'} \in Y} f (x, y) f (x^{'}, y) f (x, y^{'}) f (x^{'}, y^{'}) \leq c_{3}$ .

Proof.

(ii) $\Rightarrow$ (i) Obvious (let $u = 𝟙_{X^{'}}$ , $v = 𝟙_{Y^{'}}$ ). $c_{1} = c_{2}$ .
(i) $\Rightarrow$ (ii) Example sheet. $c_{2} = \frac{c_{1}}{12}$ .

(ii)

\Rightarrow

(iii) Suppose (iii) is false, i.e.

𝔼_{x, x^{'} \in X} 𝔼_{y, y^{'} \in Y} f (x, y) f (x^{'}, y) f (x, y^{'}) f (x^{'}, y^{'}) > c_{2},

with $c_{3} = c_{2}$ . We can rewrite as:

𝔼_{x^{'} \in X, y^{'} \in Y} 𝔼_{x \in X, y \in Y} f (x, y) \underset{v (y)}{\underset{⏟}{f (x^{'}, y)}} \underset{u (x)}{\underset{⏟}{f (x, y^{'}) f (x^{'}, y^{'})}} > c_{2} .

So there exist $x^{'} \in X$ , $y^{'} \in Y$ such that

𝔼_{x^{'} \in X, y^{'} \in Y} 𝔼_{x \in X, y \in Y} f (x, y) v (y) u (x) > c_{2},

contradiction. $c_{3} = c_{2}$

(iii) $\Rightarrow$ (ii) $\begin{array}{l} | 𝔼_{x \in X} 𝔼_{y \in Y} f (x, y) u (x) v (y) |^{2} & = | 𝔼_{y \in Y} v (y) 𝔼_{x \in X} f (x, y) u (y) |^{2} \\ \leq 𝔼_{y \in Y} | 𝔼_{x \in X} f (x, y) u (x) |^{2} \\ = 𝔼_{x \in X} u (x) u (x^{'}) 𝔼_{y \in Y} f (x, y) f (x^{'}, y) \end{array}$
So
$\begin{array}{l} | 𝔼_{x \in X} 𝔼_{y \in Y} f (x, y) u (x) v (y) |^{4} & \leq 𝔼_{x, x^{'} \in X} | 𝔼_{y \in Y} f (x, y) f (x^{'}, y) |^{2} \\ \leq c_{3} \end{array}$
$c_{2} = c_{3}^{\frac{1}{4}}$

□

Definition 1.6. Say $f : X \times Y \to [- 1, 1]$ is $𝜀$ -quasirandom if Proposition 1.5(iii) holds with $c_{3} = 𝜀^{4}$ . Say a graph $G$ on $X \times Y$ of density $δ > 0$ is $𝜀$ -quasirandom if its balanced function $f (x, y) = 𝟙_{G} (x, y) - δ$ is $𝜀$ -quasirandom (note that $𝔼 f (x, y) = 0$ ).

Proposition 1.7 (Counting Lemma). Let $G$ be a tripartite graph on vertex sets $X, Y, Z$ . Suppose $G (X, Y), G (X, Z), G (Y, Z)$ are $𝜀$ -quasirandom, with densities $δ_{X Y}, δ_{X Z}, δ_{Y Z}$ respectively. Then

| \underset{(*)}{\underset{⏟}{𝔼_{x \in X} 𝔼_{y \in Y} 𝔼_{z \in Z} 𝟙_{G} (x, y) 𝟙_{G} (x, z) 𝟙_{G} (y, z) - δ_{X Y} δ_{X Z} δ_{Y Z}}} | \leq 4 𝜀 .

Proof.

\begin{array}{l} (*) & = 𝔼_{x \in X} 𝔼_{y \in Y} 𝔼_{z \in Z} (f_{X Y} (x, y) + δ_{X Y}) (f_{X Z} (x, z) + δ_{X Z}) (f_{Y Z} (y, z) + δ_{Y Z}) - δ_{X Y} δ_{X Z} δ_{Y Z} \\ = seven terms \end{array}

For example,

𝔼_{x \in X} 𝔼_{y \in Y} 𝔼_{z \in Z} f_{X Y} (x, y) f_{X Z} (x, z) f_{Y Z} (y, z) = 𝔼_{x \in Z} 𝔼_{x \in X, y \in Y} f_{X Y} (x, y) u_{z} (x) v_{z} (y) \leq 𝜀,

by (iii) $⟹$ (ii). Similarly for the other terms, and hence we get $(*) \leq 7 𝜀$ .

We can improve it to $(*) \leq 4 𝜀$ by noticing that $3$ of the terms are zero (any of the terms of the form $f δ δ$ ). □

Definition 1.8. Suppose $X = X_{1} \cup \dots \cup X_{n}$ and $Y = Y_{1} \cup \dots \cup Y_{m}$ . Then the mean square density (msd) of a bipartite graph $G$ on $X \times Y$ relative to this partition is

\sum_{i = 1}^{n} \sum_{j = 1}^{m} \frac{| X_{i} | | Y_{j} |}{| X | | Y |} d {(G (X_{i}, Y_{j}))}^{2},

where $d (G (X_{i}, Y_{j}))$ is the density of $G (X_{i}, Y_{j})$ .

Lemma 1.9. Let $G$ be a bipartite graph on $X \times Y$ of density $δ > 0$ , and suppose it fails to be $𝜀$ -quasirandom. Then there are partitions $X = X_{1} \cup X_{2}$ , $Y = Y_{1} \cup Y_{2}$ such that the $msd$ of $G$ relative to the new partition is $δ^{2} + {(\frac{𝜀}{2})}^{8}$ .

Proof. Proposition 1.5(i) $\Rightarrow$ (iii) provides us with $X_{1} \subseteq X$ , $Y_{1} \subseteq Y$ such that

𝔼_{x \in X_{1}, y \in Y_{1}} f (x, y) > \frac{𝜀^{4}}{12} \frac{| X |}{| X_{1} |} \frac{| Y |}{| Y_{1} |} .

Let $X_{2} = X ∖ X_{1}$ , $Y_{2} = Y ∖ Y_{1}$ .

The $msd$ relative to the new partition is

\sum_{i = 1}^{2} \sum_{j = 1}^{2} \frac{| X_{i} | | Y_{i} |}{| X | | Y |} d {(G (X_{i}, Y_{j}))}^{2},

where

d (G (X_{i}, Y_{j})) = 𝔼_{x \in X_{i}, y \in Y_{j}} 𝟙_{G} (x, y) = 𝔼_{x \in X_{i}, y \in Y_{j}} (f (x, y) + δ) = δ + φ (X_{i}, Y_{j}) .

Know: $φ (X_{1}, Y_{1}) > \frac{𝜀^{4}}{12} \frac{| X |}{| X_{1} |} \frac{| Y |}{| Y_{1} |}$ . So

\begin{array}{l} \sum_{i = 1}^{2} \sum_{j = 1}^{2} \frac{| X_{i} | | Y_{j} |}{| X | | Y |} (δ^{2} + 2 δ φ (X_{i}, Y_{j}) + φ {(X_{i}, Y_{j})}^{2}) & \geq δ^{2} + 0 + \sum_{i = 1}^{2} \sum_{j = 1}^{2} \frac{| X_{i} | | Y_{j} |}{| X | | Y |} φ {(X_{i}, Y_{j})}^{2} \\ \geq δ^{2} + {(\frac{𝜀}{2})}^{8} □ \end{array}

1 The regularity lemma and applications