前提知識

グラフ理論の基本的な言葉は仮定します．

前書き

Szemerédiの正則化補題の話をします．まずその証明を示します．それから，代表的な応用例を述べます．非自明な構造を味わえるように説明していきたいと思います．
応用例から見ても面白いかもしれません．

Szemerédiの正則化補題

Szemerédiの正則化補題は，グラフ理論の定理です．言葉で説明するのは難しいのですが，元のグラフを，大体ある性質を保つように上手く分割できることを保証してくれる定理です．また，ばらばらな構造を持った複雑なグラフを，簡単なグラフで近似できるとも言えます．この定理のすごい所は，どんなグラフについても分割できる所です．本質は鳩ノ巣原理の発展版みたいな感じであるという説明もあり得るでしょう．この定理は，例えば数論など様々な数学の他分野と関連しており，大変興味深いです．

定義

定義１ (辺密度)

グラフ$G=(V,E)$について，$X,Y \subseteq V$に対して，$e_{G}(X,Y)$を$X,Y$の間にある辺の数とする．つまり，

$$e_{G}(X,Y)= \# \{ xy \in E \mid x \in X, y \in Y \}$$

です．$X \cap Y$の部分は２回数えます．辺密度 $d_{G}(X,Y)$とは，

$$d_{G}(X,Y) = \frac{e_{G}(X,Y)}{|X| \cdot |Y|}$$

です．名前の通り，辺の数を集合の大きさで割っています．

定義２ ($\epsilon$-正則ペア)

部分集合$X,Y \subseteq V$に対して，$(X,Y)$が$\epsilon$-正則ペアであるとは，
$|A| \geq \epsilon |X|$，$|B| \geq \epsilon |Y|$を満たす，任意の$A \subseteq X$，$B \subseteq Y$について，

$$|d_{G}(A,B)-d_{G}(X,Y)| \leq \epsilon$$

が成立することです．密度が場所によってあまり変わらない，つまり，一様に分布しているというイメージです．

定義３ ($\epsilon$-正則な分割)

頂点集合$V$の分割$\mathcal{P}=\{ V_1,V_2,...,V_k \}$が$\epsilon$-正則であるとは，

$$\sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則ではない}} |V_i|\cdot|V_j| \leq \epsilon |V(G)|^2$$

が成立していることです．これは，ある程度は$\epsilon$-正則ではないペアを許すが，上限は与えられているという状況です．

定理１(Szemerédiの正則化補題)

任意の$\epsilon > 0$に対して，ある$M(\epsilon)$があって，任意のグラフについて高々$M$個の$\epsilon$-正則な分割が存在する．

定理１の証明（１）

証明は実際に分割を構成するアルゴリズムを考えて示します．

アルゴリズム

[1] 最初の分割は$V$とします．
[2] 分割が$\epsilon$-正則ではない間，次の[3]，[4]を繰り返します．
[3] 各$\epsilon$-正則ではないペア$(V_i,V_j)$について，$|d_{G} (A^{i,j},A^{j,i})-d_{G}(V_i,V_j)| > \epsilon$を満たす$A^{i,j},A^{j,i}$を探し出します．
[4] $V_i$を，全ての$j$を考慮して$A^{i,j}$で分割する．

このアルゴリズムが終了するなら，$\epsilon$-正則ではない分割が得られます．

問題は，
1.本当に終了するのか，
2.どれくらい繰り返せば終わるのか，
3.終了した時の分割数はどれくらいか，です．

これをポテンシャルを通じて説明していきます．ポテンシャルを用いた説明は組み合わせ最適化でよく見られる手法です．

証明の為の準備

補題を３つ利用します．その補題で使うエネルギーをまず定義します．

部分集合$X,Y \subseteq V$,$n=|V|$について，

$$q(X,Y) :=\frac{|X||Y|}{n^2} d_{G}(X,Y)^2$$

を考えます．これを$X,Y$のエネルギーと呼びます．
また，$X,Y$の分割$\mathcal{P}_{X}= \{ X_1,...,X_k \}$,$\mathcal{P}_{Y}=\{Y_1,...,Y_l\}$について，これらのエネルギーを

$$q(\mathcal{P}_{X},\mathcal{P}_{Y}) :=\sum_{i=1}^k \sum_{j=1}^l q(X_i,Y_j)$$

とします．
さらに，同じように$V$の分割$\mathcal{P}=\{V_1,...,V_k \}$について

$$q(\mathcal{P}) :=\sum_{i=1}^k \sum_{j=1}^k q(V_i,V_j)$$

とします．
ここで１つ大切なことは，$0 \leq q(\mathcal{P}) \leq 1$であることです．

補題１

部分集合$X,Y \subseteq V$とそれらの分割について，

$$q(\mathcal{P}_{X},\mathcal{P}_{Y}) \geq q(X,Y) $$

です．また，$\mathcal{P}'$を$\mathcal{P}$のさらに細かい分割としたとき，

$$q(\mathcal{P}') \geq q(\mathcal{P}) $$

が成立します．

補題１を示します．集合$X,Y$から一様ランダムに元$x,y$を選びます．ここで，$X_i,Y_j$を$x,y$を含む分割の１つだとします．そうすると，$Z=d_{G}(X_i,Y_j)$は確率変数になります．今，

$$\mathrm{E}[Z]=\sum_{i} \sum_{j} \frac{|X_i|}{|X|}\frac{|Y_j|}{|Y|} d_{G}(X_i,Y_j) = d_{G}(X,Y)$$

になります．これは，$\sum_{i} \sum_{j}e_G(X_i,Y_j)=e_G(X,Y)$であることからも分かりますし，一様ランダムなので，期待値は全体の密度になることが推測できます．また，

$$\mathrm{E}[Z^2] = \sum_{i} \sum_{j} \frac{|X_i|}{|X|}\frac{|Y_j|}{|Y|} d_{G}(X_i,Y_j)^2=\frac{n^2}{|X||Y|} q(\mathcal{P}_{X},\mathcal{P}_{Y})$$

です．ここで，Jensenの不等式$\mathrm{E}[Z^2] \geq \mathrm{E}[Z]^2$より，

$$q(\mathcal{P}_{X},\mathcal{P}_{Y}) \geq q(X,Y) $$

が成立します．また，これを複数回用いることで，すぐに

$$q(\mathcal{P}') \geq q(\mathcal{P}) $$

が分かります．

補題２

$(X,Y)$は$\epsilon$-正則ではないとします．ここで，$X' \subseteq X,Y' \subseteq Y$が$|d_{G} (X',Y')-d_{G}(V_i,V_j)| > \epsilon$になっているとします．このとき，

$$q(\{X',X \setminus X' \},\{Y',Y \setminus Y' \}) > q(X,Y) + \epsilon^4 \frac{|X||Y|}{n^2}$$

が成り立ちます．

補題２を示します．左辺は分割同士のエネルギーです．
先ほどと同じように，集合$X,Y$から一様ランダムに元$x,y$を選びます．確率変数$Z$も$\{X',X \setminus X' \},\{Y',Y \setminus Y' \}$のうち，$x,y$を含むもの同士の辺密度とします．このとき，

$$\mathrm{E}[Z]= d_{G}(X,Y),$$$$\mathrm{E}[Z^2]=\frac{n^2}{|X||Y|} q(\{X',X \setminus X' \},\{Y',Y \setminus Y' \})$$

です．
これより，

$$\mathrm{Var}[Z] = \mathrm{E}[Z^2] -\mathrm{E}[Z]^2 = \frac{n^2}{|X||Y|} \left( q(\{X',X \setminus X' \},\{Y',Y \setminus Y' \}) - q(X,Y)) \right)$$

です．
また，$|Z - \mathrm{E}[Z]|$が$|d_{G}(X',Y')-d_{G}(X,Y)|$と一致する確率は，$\frac{|X'|}{|X|} \cdot \frac{|Y'|}{|Y|}$で，これを考えると，

$$\begin{aligned} \mathrm{Var}[Z] &= \mathrm{E}[|Z - \mathrm{E}[Z]|^2] \\ &\geq \frac{|X'|}{|X|} \cdot \frac{|Y'|}{|Y|} \cdot |d_{G}(X',Y')-d_{G}(X,Y)| \\ & > \epsilon^4 \end{aligned}$$

になります．ここで期待値の線形性と，$|X'|>\epsilon |X|$,$|Y'|>\epsilon |Y|$と$(X,Y)$は$\epsilon$-正則ではなかったことを用いています．以上から，補題２が示されました．

補題３

$V$の分割$\mathcal{P}=\{V_1,...,V_k\}$が$\epsilon$-正則ではないとします．このとき，各$V_i$を高々$2^k$個に，$\mathcal{P}$をさらに分割する分割$\mathcal{Q}$があって，さらに，

$$q(\mathcal{Q}) \geq q(\mathcal{P}) +\epsilon^5$$

を満たします．

補題３の証明を説明します．$\epsilon$-正則ではないペア$(V_i,V_j)$を考えます．こういうペアは存在します．さらに，正則にしない部分集合を$A^{ij},A^{ji}$とします．これは，アルゴリズムの中に出てくるものと同じです．分割$\mathcal{Q}$を，アルゴリズムと同じく，$A^{ij}$に関して分割したものとします．そうすると，各$V_i$は多くても$2^k$に分けられることになります．
$\mathcal{Q}_{V_i}$を，分割$\mathcal{Q}$の中で，元々$V_i$であった集合族とします．まず，

$$\begin{aligned} q(\mathcal{Q}) &= \sum_{(i,j)\in[k]^2} q(\mathcal{Q}_{V_i},\mathcal{Q}_{V_j}) \\ &= \sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則}} q(\mathcal{Q}_{V_i},\mathcal{Q}_{V_j}) +\sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則ではない}} q(\mathcal{Q}_{V_i},\mathcal{Q}_{V_j}) \\ & \geq \sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則}} q(V_i,V_j) +\sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則ではない}} q(\{A^{ij},V_i \setminus A^{ij} \},\{A^{ji},V_j \setminus A^{ji} \}) \end{aligned}$$

になります．ここで，３行目の不等式は，補題１から分かることで，細かく分割をすると，エネルギーが増加するというものです．$\mathcal{Q}_{V_i}$は$A^{ij}$で分割されています．
さらに，補題２より，上の最後の式の一番右の式に不等式が適応できて，

$$q(\mathcal{Q}) > \sum_{(i,j)\in[k]^2} q(V_i,V_j) + \sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則ではない}} \epsilon^4 \frac{|X||Y|}{n^2}$$

になります．ここで，分割$\mathcal{P}$が$\epsilon$-正則ではないので，

$$\sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon-正則ではない}} \epsilon^4 \frac{|X||Y|}{n^2} > \epsilon^5$$

が成立します．これで補題３が示されました．

定理１の証明（２）

３つの補題から，定理を証明します．補題３からアルゴリズムが進む毎にエネルギーは$\epsilon^5$ずつ増えます．任意の分割で$0 \leq q(\mathcal{P}) \leq 1$が成立するので，アルゴリズムは少なくとも$\epsilon^{-5}$ステップで終了することが分かります．また，毎回分割は$k2^k \leq 2^{2^k}$増えていくので，分割の個数は$\sum_{k=1}^{\epsilon^{-5}}2^{2^k}$で上から抑えられます．これを$M$とします．証明完了です．

Szemerédiの正則化補題の応用

Szemerédiの正則化補題は証明されましたが，ピンとこないと思います．Distelのグラフ理論の本にも書いてありますが，Szemerédiの正則化補題はやはり，適応例や，応用を見た方がイメージが得られやすいです．たくさんの応用が知られていますが，ここでは，極値グラフ理論における三角形の話と，それを用いれば示すことができる，数論の話を紹介したいと思います．

定理２（三角形除去補題）

頂点数$n$のグラフ$G=(V,E)$を考える．任意の$\epsilon>0$について，ある$\delta>0$が存在して，$\delta n^3$個以下の三角形を持つ任意のグラフは，高々$\epsilon n^2$個の辺の除去によって，三角形を全く持たないグラフにすることができる．

（コメント）
意味が伝わりにくいかもしれませんが，三角形の個数が$o(n^3)$で増えていっても，三角形の除去は$o(n^2)$で良いということです．逆に，辺を複雑に絡ませれば，辺をそこまで増やさなくても，三角形を急激に増やせるというイメージです．嬉しい定理だと思います．これの証明はSzemerédiの正則化補題に基いて作られた分割を利用して，辺の削除を実際に行うというものです．証明を行う前に，三角形数え上げ補題というものを説明する必要があります．

定理２の証明の準備（三角形数え上げ補題）

グラフ$G$の頂点部分集合$X,Y,Z \subseteq V$で，$(X,Y),(Y,Z),(Z,X)$がある共通の$\epsilon$に対して，それぞれ$\epsilon$-正則なペアになっているものを考える．もし，$d_G(X,Y),d_G(Y,Z),d_G(Z,X) \geq 2 \epsilon$が成立するなら，$G$の辺を使って作られる三角形$(x,y,z) \in X \times Y \times Z$は，少なくとも

$$(1-2 \epsilon) \epsilon^3 \cdot |X|\cdot|Y|\cdot|Z|$$

個存在する．

（三角形数え上げ補題の証明）
この三角形数え上げ補題を証明していきたいと思います．
まず，$(X,Y)$が$\epsilon$-正則という仮定から，「$Y$の中で$(d_G(X,Y)-\epsilon)|Y|$より小さい$Y$の頂点たちと繋がっている$X$の頂点の個数は，$\epsilon |X|$よりも小さい．」ということが分かります．これは，少し頭を使う必要があります．$\epsilon |X|$以上の頂点がそのように繋がっていたとします．そうすると，その部分集合を$X'$として，ペア$(X',Y)$の辺密度$d_G(X',Y)$は，$\frac{|X'|(d_G(X,Y)-\epsilon)|Y|}{|X'||Y|}=d_G(X,Y)-\epsilon$より小さくなります．これは，$(X,Y)$が$\epsilon$-正則ペアであるという条件と矛盾します．
$(Z,X)$でも同じことを考えられます．ここから，
「$Y$の中で$(d_G(X,Y)-\epsilon)|Y|$以上の頂点たちと繋がっていて，かつ，$Z$の中で$(d_G(Z,X)-\epsilon)|Z|$以上の頂点たちと繋がっているような，$X$の頂点の個数は，$(1-2 \epsilon)|X|$個以上である」ことが分かります．$(1-2 \epsilon)|X|$は$|X|$から$\epsilon|X|$を２回引いた結果です．
次に，$X$の1頂点からそれぞれ$Y,Z$へ行った2頂点の間にどれくらい辺があるかを数えます．ここで，仮定より，$(d_G(X,Y)-\epsilon)|Y|\geq \epsilon |Y|$かつ，$(d_G(Z,X)-\epsilon)|Z|\geq \epsilon |Z|$より，$(Y,Z)$の$\epsilon$-正則性より，この2頂点の間の辺密度は，$d_G(Y,Z)-\epsilon$以上であることが分かります．
以上の結果から，三角形の個数は少なくとも，

$$(1-2 \epsilon) (d_G(X,Y)-\epsilon)(d_G(Y,Z)-\epsilon)(d_G(X,Z)-\epsilon) \cdot |X|\cdot|Y|\cdot|Z| \geq (1-2 \epsilon) \epsilon^3 \cdot |X|\cdot|Y|\cdot|Z|$$

個は存在します．

定理２の証明

辺の除去の手順を説明します．それに従って除去をすれば全ての三角形が消えるというのを数え上げの補題を使って示すことができます．
まず，Szemerédiの正則化補題を用いて，グラフ$G$を$\epsilon/4$-正則に分割します．分割を$\{V_1,V_2,...,V_M \}$と書きます．
次に，ペア$(V_i,V_j)$が下の３条件のどれか１つでも満たせば，その間の辺を全て除去するという操作を考えます．
(条件１)　$(V_i,V_j)$が $\epsilon/4$-正則ではない．
(条件２)　辺密度について，$d_G(V_i,V_j) \leq \epsilon/2$．
(条件３)　$V_i,V_j$のどちらかが，高々$\frac{\epsilon}{4M}n$個の頂点しか持たない．

さて，このときどれくらいの辺が消去されることになるのかを調べにいきます．
まず条件１では，分割の$\epsilon/4$-正則性より，

$$\sum_{ \substack{ (i,j) \in [k]^2, \\ (V_i,V_j)は\epsilon/4-正則ではない}} |V_i|\cdot|V_j| \leq \frac{\epsilon}{4} n^2$$

より，高々$\frac{\epsilon}{4} n^2$個しか辺は消されません．
条件２では，$\sum_{ \substack{ (i,j) \in [k]^2, \\ d_G(V_i,V_j) \leq \epsilon/2}} d_G(v_i,V_j)|V_i|\cdot|V_j| \leq \frac{\epsilon}{2} n^2$
より，高々$\frac{\epsilon}{2} n^2$個．
条件３では，高々$n \cdot (\frac{\epsilon}{4M}n)\cdot M=\frac{\epsilon}{4} n^2$個です．

よって，辺の除去は合計しても$o(n^2)$だけしか行われません．あとは，$\delta$を上手く設定してやれば，この操作を終了したときに三角形が全て消えることを示すことができます．

ここで，上の辺の除去の操作を終えた後も，三角形が存在していたと仮定します．その三角形を含む分割をそれぞれ$V_i,V_j,V_k$とします．重複していても良いです．さて，辺が残っている場所なので，条件１と条件２を満たしません．故に，$V_i,V_j,V_k$は三角形数え上げ補題の仮定を満たします．これから，グラフには他にも少なくとも，

$$\left( 1-\frac{\epsilon}{2} \right) \left( \frac{\epsilon}{4} \right)^3 |V_i|\cdot |V_j| \cdot |V_k|$$

個の三角形が存在します．また，条件３を満たさないので，結局，

$$\left( 1-\frac{\epsilon}{2} \right) \left( \frac{\epsilon}{4} \right)^3 \left( \frac{\epsilon}{4M} \right)^3 n^3$$

個以上の三角形が存在することになります．ここで，$\delta$を

$$\delta < \frac{1}{6}\left( 1-\frac{\epsilon}{2} \right) \left( \frac{\epsilon}{4} \right)^3 \left( \frac{\epsilon}{4M} \right)^3$$

と設定しておけば，元のグラフには$\delta n^3$個以下の三角形しかなかったので，矛盾になります．よって，三角形は全て除去されます．
ここでポイントは，この$\delta$が$n$によらず，$\epsilon$にのみ依存するように取れるという点です．

（コメント）
定理２から他にも面白い結果が得られます．後で，Rothの定理という数論での応用に用いることができるものです．

定理３

$n$頂点のグラフ$G$について，どの辺も丁度１つの三角形に含まれるものとする．このとき，$G$は$o(n^2)$の辺を持つ．

（定理３の証明）
定理３を証明します．すぐ終わります．今更ですが，$o(n^2)$は，$n \to \infty$の時に$(Gの辺数)/n^2 \to 0$になるということです．
$G$の辺数を$m$とすると，三角形は$m/3$個．$m < n^2$より，このグラフは$o(n^3)$の三角形を持つと言えます．つまり，定理２から，$o(n^2)$の辺の除去で三角形は全て消えます．よって，$m/3 \leq o(n^2)$であるので，$m$は$o(n^2)$です．

定理４（Rothの定理）

任意の$\epsilon>0$について，ある$N(\epsilon)>0$があって，$N$以上の任意の$n$で，$|A|\geq \epsilon n$を満たす任意の部分集合$A \subseteq [n]$は，長さ$3$の等差数列を持つ．

（定理４の証明）
定理４で，急に全く違う話題になったような気がします．これが，Szemerédiの正則化補題の数論への応用の一端を知れる簡単な例になります．確かに，じっと見ていると，どことなくSzemerédiの正則化補題の面影を見ることができる気がします．
定理３を利用して，定理４を証明します．ここでは，$[n]$の部分集合$A$に長さ$3$の等差数列が一切含まれないとき，$|A|=o(n)$になることを示します．
$M=2n+1$として，$\mathbb{Z}/M\mathbb{Z}$のコピーを３つ$X,Y,Z$を作ります．$X,Y,Z$の元が頂点になるように，頂点数$6n+3$のグラフを作ります．また，辺は次のように作ります．
$xy \in E \Leftrightarrow y-x \in A$，
$yz \in E \Leftrightarrow z-y \in A$，
$zx \in E \Leftrightarrow (z-x)/2 \in A$．
ここで，$x \in X,y\in Y,z \in Z$です．三角形を作ろうとして，グラフが出来上がります．$\mathbb{Z}/M\mathbb{Z}$という設定から，全ての$A$の元が考えられます．さて，今，

$$(x,y,z)が三角形 \Leftrightarrow y-x \in A\ \&\ \frac{z-x}{2} \in A\ \&\ z-y \in A$$

になります．簡単な計算から，$y-x, \frac{z-x}{2}, z-y$は等差数列になることが分かります．$A$には長さ3の等差数列は含まれないので，$y-x=\frac{z-x}{2}=z-y$になります．つまり，$x,y,z$が等差数列になります．

$$(x,y,z)が三角形 \Leftrightarrow x,y,zが等差数列$$

です．
ある辺$e=xy$に着目したとき，$(x,y,z)$が三角形になるには，等差数列の関係より，$z$は一意的に定まります．故に，$G$の全ての辺は１つの三角形にしか含まれないことが分かります．ここで，定理３より辺数は$o(n^2)$になります．
さて，$G$の構成から辺数は$3 \cdot |A| \cdot M$と書けるので，$M=o(n)$から，$|A|=o(n)$を得ます．最後の$3$をかけているのは，三角形の分です．

後書き

Szemerédiの正則化補題を紹介しましたが，最後の定理４の一般化として，Szemerédiの定理というものが存在します．これは，ある部分集合に長さ$k$の等差数列が含まれるかどうかを教えてくれます．きちんと言うと，「長さ$k$の等差数列を一切持たないなら，$|A|=o(n)$である」というものです．Rothを一般の$k$にしても成立します．
また，Green-Taoの定理という凄い定理があるようです．これは，「素数の列には任意の長さの等差数列が存在する」という定理です．シンプルでパワフルなステートメントです．
少し長い記事になってしまいました．

参考文献

$\cdot$MITのLecture note( https://ocw.mit.edu/courses/mathematics/18-217-graph-theory-and-additive-combinatorics-fall-2019/index.htm )

$\cdot$E. Szemerédi, "On sets of integers containing no k elements in arithmetic progression", Acta Arithmetica. 27, 1975, 199–245.

$\cdot$B. Green, T. Tao, "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics. 167 (2), 2008, 481–547.