Szemerédiの正則性補題
概要
Szemerédiの正則性補題（Szemerédi's regularity lemma）とは、任意の $\varepsilon>0$ に対し $\varepsilon$ だけで決まる $M$ があって、どの有限グラフの頂点集合も $M$ 個以下の部分に分割でき、頂点の組の割合で $\varepsilon$ 以下を除いて部分の組が ε-正則（大きな部分集合どうしの辺の密度が全体の密度とほぼ等しい）になる、という定理である。分割のエネルギーが細分のたびに $\varepsilon^5$ を超えて増えることから証明され、$M$ は $2$ の冪を高さ $2\lceil\varepsilon^{-5}\rceil$ まで重ねた塔にとれる。Gowers により塔の形は避けられない。三角形の数え上げ補題と組み合わせて三角形除去補題などを導く正則性の方法の基礎である。
前提知識: グラフ, 部分グラフ, Cauchy–Schwarzの不等式, 極値グラフ理論
Szemerédi の正則性補題（Szemerédi's regularity lemma）は、どんなに大きなグラフでも、頂点の集合を「グラフの大きさによらない個数」の部分に分けると、ほとんどの部分の組のあいだで辺がランダムに引かれたかのように一様に分布する、という定理である。1970 年代に E. Szemerédi が導入した。分けた部分の組ごとに辺の密度だけを記録すると、もとのグラフは有限個の数の表で近似できる。この近似の上で部分グラフの個数を数える 数え上げ補題 と組み合わせた議論は 正則性の方法 とよばれ、極値グラフ理論 の中心的な手法の一つになっている。
この記事では、ε-正則な対と ε-正則分割を定義し、正則性補題を エネルギー増分 の議論で証明する。証明から得られる部分の個数の上界は、$2$ の冪を高さ $2\lceil\varepsilon^{-5}\rceil$ まで重ねた塔の形になる。W. T. Gowers は、この塔の形が避けられないことを示した（主張だけを述べる）。最後に、3 つの ε-正則な対の上で三角形を数える 三角形の数え上げ補題 を証明する。これを正則性補題と組み合わせると 三角形除去補題 が得られる。
辺の密度と ε-正則性
この記事では、グラフ $G=(V,E)$ は頂点が $n\ge1$ 個の有限の単純グラフとする。頂点の部分集合 $X,Y\subset V$（交わってもよい）について
$$
e(X,Y):=\bigl\lvert\{(x,y)\in X\times Y\mid xy\in E\}\bigr\rvert
$$
とおく。順序を付けた組を数えるので、$X\cap Y$ の中の辺は 2 回数えられ、$e(V,V)=2\lvert E\rvert$ である。$X,Y$ が空でないとき、辺の密度 を
$$
d(X,Y):=\frac{e(X,Y)}{\lvert X\rvert\,\lvert Y\rvert}\in[0,1]
$$
で定める。$e(X,Y)=e(Y,X)$ なので $d(X,Y)=d(Y,X)$ である。$x\in V$ に隣接する頂点の集合を $N(x)$ と書く。
$\varepsilon>0$ とし、$U,W\subset V$ を空でない集合とする。$\lvert A\rvert\ge\varepsilon\lvert U\rvert$、$\lvert B\rvert\ge\varepsilon\lvert W\rvert$ を満たすすべての $A\subset U$、$B\subset W$ について
$$
\bigl\lvert d(A,B)-d(U,W)\bigr\rvert\le\varepsilon
$$
が成り立つとき、対 $(U,W)$ は ε-正則（$\varepsilon$-regular）であるという。ε-正則でないとき、$\lvert A\rvert\ge\varepsilon\lvert U\rvert$、$\lvert B\rvert\ge\varepsilon\lvert W\rvert$、$\lvert d(A,B)-d(U,W)\rvert>\varepsilon$ を満たす $(A,B)$ を、正則でないことの 証拠 という。
$\varepsilon\le1$ なら条件の $A,B$ は空でないので $d(A,B)$ は定まる。$\varepsilon>1$ なら条件を満たす $A$ がないので、どの対も ε-正則である。$d$ が対称なので、$(U,W)$ が ε-正則であることと $(W,U)$ が ε-正則であることは同じであり、$(A,B)$ が $(U,W)$ の証拠なら $(B,A)$ は $(W,U)$ の証拠である。
大きさの条件を外すと、$A=\{x\}$、$B=\{y\}$ で $d(A,B)$ は $0$ か $1$ になり、辺をもつ対はほとんど正則にならない。ε-正則性は大きな部分集合どうしの密度が全体の密度とほぼ同じことを求めている。
$V$ の分割 $\mathcal P=\{V_1,\dots,V_k\}$（各 $V_i$ は空でない）が
$$
\sum_{\substack{(i,j)\in\{1,\dots,k\}^2\\ (V_i,V_j)\text{ は ε-正則でない}}}\lvert V_i\rvert\,\lvert V_j\rvert\le\varepsilon n^2
$$
を満たすとき、$\mathcal P$ を ε-正則分割 という。和は順序を付けた組 $(i,j)$ にわたり、$i=j$ も含む。
左辺は、ε-正則でない部分の組のあいだにある頂点の組 $(x,y)\in V\times V$ の個数である。すなわち、ε-正則分割では、頂点の組の割合で $\varepsilon$ 以下を除いて、組は ε-正則な部分のあいだにある。$\varepsilon\ge1$ なら左辺は $n^2$ 以下なので、どの分割も ε-正則分割である。
- $U,W$ が交わらず、$U$ のどの頂点も $W$ のどの頂点とも隣接するとき（完全な対）、どの $A,B$ でも $d(A,B)=1=d(U,W)$ である。$e(U,W)=0$ のとき（空の対。$U=W$ でもよい）は $d(A,B)=0=d(U,W)$ である。どちらもすべての $\varepsilon>0$ について ε-正則である。
- $t\ge1$ とし、$V=U_1\cup U_2\cup W_1\cup W_2$（どれも $t$ 個の頂点で互いに交わらない）とし、辺を $U_1$ と $W_1$ のあいだにすべて引き、ほかには引かないグラフを考える。$n=4t$ で、$e(V,V)=2t^2$ なので $d(V,V)=1/8$ である。$0<\varepsilon\le1/4$ のとき、$A=U_1$、$B=W_1$ は $\lvert A\rvert=\lvert B\rvert=n/4\ge\varepsilon n$、$d(A,B)=1$ を満たすので、$(V,V)$ は ε-正則でなく、1 つの部分からなる分割 $\{V\}$ は ε-正則分割でない（左辺は $n^2>\varepsilon n^2$）。一方、分割 $\{U_1,U_2,W_1,W_2\}$ では、部分の組はどれも完全な対か空の対なので、すべての $\varepsilon>0$ について ε-正則分割である。
正則性補題
$T(0):=1$、$T(m+1):=2^{T(m)}$ と定める。$T(1)=2$、$T(2)=4$、$T(3)=16$、$T(4)=65536$ であり、$T(m)$ は $2$ の冪を高さ $m$ まで重ねた塔（累乗の塔）である。
$\varepsilon>0$ とし、$M(\varepsilon):=T\bigl(2\lceil\varepsilon^{-5}\rceil\bigr)$ とおく。このとき、頂点が $1$ 個以上のどの有限の単純グラフも、部分が $M(\varepsilon)$ 個以下の ε-正則分割をもつ。
$M(\varepsilon)$ が $\varepsilon$ だけで決まり、頂点の個数 $n$ によらないことが要点である（1 点ずつ $n$ 個に分ければ ε-正則分割になるが、部分の個数が $n$ とともに増える）。証明（prf-reg-main）では、分割の「エネルギー」が、正則でない対の証拠を使って細分するたびに $\varepsilon^5$ を超えて増え、しかも $1$ を超えないことを使う。
エネルギー
空でない $U,W\subset V$ について $q(U,W):=\dfrac{\lvert U\rvert\,\lvert W\rvert}{n^2}\,d(U,W)^2$ とおく。$U$ の分割 $\mathcal P_U=\{U_1,\dots,U_a\}$ と $W$ の分割 $\mathcal P_W=\{W_1,\dots,W_b\}$（部分は空でない）について
$$
q(\mathcal P_U,\mathcal P_W):=\sum_{s=1}^a\sum_{t=1}^bq(U_s,W_t)
$$
とおき、$V$ の分割 $\mathcal P$ の エネルギー を $q(\mathcal P):=q(\mathcal P,\mathcal P)$ と定める。
$\mathcal P=\{V_1,\dots,V_k\}$ なら $q(\mathcal P)=\sum_{i,j}\frac{\lvert V_i\rvert\lvert V_j\rvert}{n^2}d(V_i,V_j)^2$ で、$d\le1$ と $\sum_{i,j}\lvert V_i\rvert\lvert V_j\rvert=n^2$ から $0\le q(\mathcal P)\le1$ である。分割 $\mathcal Q$ の各部分が $\mathcal P$ のどれかの部分に含まれるとき、$\mathcal Q$ は $\mathcal P$ の 細分 であるという。
$\mathcal P_U=\{U_1,\dots,U_a\}$、$\mathcal P_W=\{W_1,\dots,W_b\}$ を空でない $U,W$ の分割とし、$w_{st}:=\dfrac{\lvert U_s\rvert\lvert W_t\rvert}{\lvert U\rvert\lvert W\rvert}$ とおく。このとき
$$
q(\mathcal P_U,\mathcal P_W)-q(U,W)=\frac{\lvert U\rvert\lvert W\rvert}{n^2}\sum_{s,t}w_{st}\bigl(d(U_s,W_t)-d(U,W)\bigr)^2\ge0
$$
である。
$e(U,W)=\sum_{s,t}e(U_s,W_t)$ を $\lvert U\rvert\lvert W\rvert$ で割ると、$d:=d(U,W)$、$d_{st}:=d(U_s,W_t)$ として $d=\sum_{s,t}w_{st}d_{st}$ であり、$\sum_{s,t}w_{st}=1$ である。よって
$$
\sum_{s,t}w_{st}(d_{st}-d)^2=\sum_{s,t}w_{st}d_{st}^2-2d\sum_{s,t}w_{st}d_{st}+d^2=\sum_{s,t}w_{st}d_{st}^2-d^2
$$
である。両辺に $\lvert U\rvert\lvert W\rvert/n^2$ を掛けると、右辺は $\sum_{s,t}\lvert U_s\rvert\lvert W_t\rvert d_{st}^2/n^2-\lvert U\rvert\lvert W\rvert d^2/n^2=q(\mathcal P_U,\mathcal P_W)-q(U,W)$ になる。$\square$
$\sum w_{st}d_{st}^2\ge(\sum w_{st}d_{st})^2$ は重み付きの Cauchy–Schwarzの不等式 でもあり、分散 が $0$ 以上であることと同じである。
$\mathcal Q_U$ が $U$ の分割 $\mathcal P_U$ の細分、$\mathcal Q_W$ が $W$ の分割 $\mathcal P_W$ の細分なら $q(\mathcal Q_U,\mathcal Q_W)\ge q(\mathcal P_U,\mathcal P_W)$ である。とくに $V$ の分割 $\mathcal Q$ が $\mathcal P$ の細分なら $q(\mathcal Q)\ge q(\mathcal P)$ である。
$\mathcal P_U$ の部分 $U'$ と $\mathcal P_W$ の部分 $W'$ ごとに、$\mathcal Q_U$ の部分のうち $U'$ に含まれるものは $U'$ の分割をなし、$W'$ についても同じである。この 2 つの分割に lem-reg-refine を当てて $U',W'$ について足すと、左辺は $q(\mathcal Q_U,\mathcal Q_W)$、右辺は $q(\mathcal P_U,\mathcal P_W)$ 以上になる。$\square$
$(U,W)$ が ε-正則でなく、$(A,B)$ がその証拠とする。$U$ の分割 $\{A,U\setminus A\}$ と $W$ の分割 $\{B,W\setminus B\}$（空の部分は除く）について
$$
q\bigl(\{A,U\setminus A\},\{B,W\setminus B\}\bigr)>q(U,W)+\varepsilon^4\frac{\lvert U\rvert\lvert W\rvert}{n^2}
$$
である。
lem-reg-refine の右辺の和のうち、組 $(A,B)$ の項だけを残すと、$w=\frac{\lvert A\rvert\lvert B\rvert}{\lvert U\rvert\lvert W\rvert}\ge\varepsilon^2$、$(d(A,B)-d(U,W))^2>\varepsilon^2$ なので、和は $\varepsilon^4$ より大きい。ほかの項は $0$ 以上である。$\square$
$V$ の分割 $\mathcal P=\{V_1,\dots,V_k\}$ が ε-正則分割でなければ、$\mathcal P$ の細分 $\mathcal Q$ で、各 $V_i$ が $2^{k+1}$ 個以下の部分に分かれ、
$$
q(\mathcal Q)>q(\mathcal P)+\varepsilon^5
$$
を満たすものがある。
$I$ を、$(V_i,V_j)$ が ε-正則でない組 $(i,j)$ の集合とする。各 $(i,j)\in I$ の証拠 $(A_{ij},B_{ij})$ を、$i\ne j$ では $A_{ji}=B_{ij}$、$B_{ji}=A_{ij}$ となるようにとり、各 $V_i$ を、$V_i$ の中にある証拠の集合（$k+1$ 個以下）すべてで切り分けた分割 $\mathcal Q_i$ を作る。$\mathcal Q:=\mathcal Q_1\cup\dots\cup\mathcal Q_k$ とおく。
細分の作り方を開く
$(i,j)\in I$ と $(j,i)\in I$ は同値である。$i< j$ となる $(i,j)\in I$ について証拠 $(A_{ij},B_{ij})$ をとり、$A_{ji}:=B_{ij}$、$B_{ji}:=A_{ij}$ とおくと、$(A_{ji},B_{ji})$ は $(V_j,V_i)$ の証拠である。$(i,i)\in I$ については証拠 $(A_{ii},B_{ii})$ をとる（$A_{ii}\ne B_{ii}$ でもよい）。各 $i$ について、$V_i$ の部分集合 $A_{ij}$（$(i,j)\in I$）と $B_{ii}$（$(i,i)\in I$ のとき）は合わせて $k+1$ 個以下である。$V_i$ の 2 点を、これらのどの集合についても両方が属するか両方が属さないときに同じ部分に入れた分割を $\mathcal Q_i$ とすると、部分は「各集合に属するか属さないか」の選び方で決まるので $2^{k+1}$ 個以下である。
$(i,j)\in I$ のとき、$\mathcal Q_i$ は $\{A_{ij},V_i\setminus A_{ij}\}$ の細分であり、$\mathcal Q_j$ は $\{B_{ij},V_j\setminus B_{ij}\}$ の細分である（$i\ne j$ なら $B_{ij}=A_{ji}$、$i=j$ なら $B_{ii}$ を使ったから）。cor-reg-monotone と lem-reg-boost-pair から
$$ q(\mathcal Q)=\sum_{i,j}q(\mathcal Q_i,\mathcal Q_j)\ge\sum_{(i,j)\notin I}q(V_i,V_j)+\sum_{(i,j)\in I}q\bigl(\{A_{ij},V_i\setminus A_{ij}\},\{B_{ij},V_j\setminus B_{ij}\}\bigr) $$
であり、右辺は $q(\mathcal P)+\varepsilon^4\sum_{(i,j)\in I}\lvert V_i\rvert\lvert V_j\rvert/n^2$ より大きい（$I$ は空でない）。$\mathcal P$ は ε-正則分割でないので $\sum_{(i,j)\in I}\lvert V_i\rvert\lvert V_j\rvert>\varepsilon n^2$ であり、$q(\mathcal Q)>q(\mathcal P)+\varepsilon^5$ を得る。$\square$
証拠を 1 組ずつ使って細分を繰り返すと、1 回の増加は lem-reg-boost-pair の $\varepsilon^4\lvert V_i\rvert\lvert V_j\rvert/n^2$ だけで、部分が小さくなるとこの量も小さくなるので、繰り返しの回数を $\varepsilon$ だけで押さえられない。すべての証拠を同時に使うと増加量を $I$ 全体で足し合わせられ、正則でない組の割合が $\varepsilon$ を超えることから、増加は $\varepsilon^5$ を超える。
正則性補題の証明
段 1（繰り返し）。 $\mathcal P_0:=\{V\}$ とする。$\mathcal P_m$ が ε-正則分割でない間は、lem-reg-boost-partition の細分 $\mathcal Q$ を $\mathcal P_{m+1}$ とする。$q(\mathcal P_0)\ge0$ で、1 回ごとにエネルギーは $\varepsilon^5$ より多く増えるので、$m\ge1$ について $q(\mathcal P_m)>m\varepsilon^5$ である。$q(\mathcal P_m)\le1$ なので $m<\varepsilon^{-5}$ であり、繰り返しは $\lceil\varepsilon^{-5}\rceil-1$ 回以下で止まる。止まったときの分割は ε-正則分割である。
段 2（部分の個数）。 $\mathcal P_m$ の部分の個数を $k_m$ とすると、$k_0=1$ で、$k_{m+1}\le k_m2^{k_m+1}$ である。整数 $k\ge1$ について $k\le2^{k-1}$ なので $k\,2^{k+1}\le2^{2k}$ であり、また $2k\le2^k$ である。$k_m\le T(2m)$ と仮定すると、$T$ は増加なので
$$
k_{m+1}\le2^{2k_m}\le2^{2^{k_m}}\le2^{2^{T(2m)}}=T(2m+2)
$$
である。よって帰納法により $k_m\le T(2m)$ であり、止まったときの部分の個数は $T\bigl(2(\lceil\varepsilon^{-5}\rceil-1)\bigr)\le M(\varepsilon)$ 以下である。$\square$
証明は「分割が少しずつ正則に近づく」ことを示していない。エネルギーは正則性の度合いではなく、繰り返しの回数を押さえるためだけに使われている。
- 塔の形は避けられない：ある定数 $c>0$ があって、十分小さいどの $\varepsilon>0$ についても、部分が $T(\lceil\varepsilon^{-c}\rceil)$ 個未満の ε-正則分割をもたないグラフが存在する。これは Gowers（1997 年）による（Zha23 Theorem 2.1.17、p. 60 に主張がある。この記事では証明しない）。したがって thm-reg-main の $M(\varepsilon)$ を、$\varepsilon^{-1}$ の冪や指数関数を有限回重ねたもので置き換えることはできない。
- 均等な分割：任意の $\varepsilon>0$ と $m_0\ge1$ について、ある $M'$ があって、頂点が $m_0$ 個以上のどのグラフも、部分の大きさの差が $1$ 以下で部分の個数 $k$ が $m_0\le k\le M'$ を満たす ε-正則分割をもつ（Zha23 Theorem 2.1.20、p. 61 に主張と証明の概略がある。この記事では証明しない）。証明は prf-reg-main の各段で分割を均等に切り直し、そのときのエネルギーの減少が小さいことを確かめるものである。
- 初めの分割を指定する：prf-reg-main の $\mathcal P_0$ を、部分が $k$ 個以下の任意の分割に替えても、同じ議論で $\mathcal P_0$ の細分である ε-正則分割が得られ、部分の個数は $\varepsilon$ と $k$ だけで決まる上界をもつ（Zha23 Theorem 2.1.19、p. 61）。
三角形の数え上げ補題
正則性補題で得た分割の上で部分グラフを数えるのが数え上げ補題である。3 つの対が ε-正則なら、三角形の個数は、辺の密度が同じランダムなグラフで期待される個数 $d(X,Y)d(X,Z)d(Y,Z)\lvert X\rvert\lvert Y\rvert\lvert Z\rvert$ に近い値以上になる。
$(X,Y)$ が ε-正則な対なら、$\lvert N(x)\cap Y\rvert<(d(X,Y)-\varepsilon)\lvert Y\rvert$ を満たす $x\in X$ は $\varepsilon\lvert X\rvert$ 個未満である。
$\varepsilon>1$ なら $\lvert X\rvert<\varepsilon\lvert X\rvert$ なので明らかである。$\varepsilon\le1$ とし、そのような $x$ の集合を $A$ とする。$\lvert A\rvert\ge\varepsilon\lvert X\rvert$ なら、$B:=Y$ は $\lvert B\rvert\ge\varepsilon\lvert Y\rvert$ を満たし、$e(A,Y)=\sum_{x\in A}\lvert N(x)\cap Y\rvert<\lvert A\rvert(d(X,Y)-\varepsilon)\lvert Y\rvert$ から $d(A,Y)< d(X,Y)-\varepsilon$ となって、$(X,Y)$ が ε-正則であることに反する。$\square$
$\varepsilon>0$ とし、$X,Y,Z\subset V$ を空でない集合（交わってもよい）とする。$(X,Y)$、$(Y,Z)$、$(Z,X)$ がどれも ε-正則で、$d(X,Y),d(X,Z),d(Y,Z)\ge2\varepsilon$ ならば、
$$
\bigl\lvert\{(x,y,z)\in X\times Y\times Z\mid xy,\,yz,\,zx\in E\}\bigr\rvert\ge(1-2\varepsilon)\bigl(d(X,Y)-\varepsilon\bigr)\bigl(d(X,Z)-\varepsilon\bigr)\bigl(d(Y,Z)-\varepsilon\bigr)\lvert X\rvert\lvert Y\rvert\lvert Z\rvert
$$
である。
$\varepsilon\ge1/2$ なら右辺は $0$ 以下なので、$\varepsilon<1/2$ とする。lem-reg-degree を $(X,Y)$ と $(X,Z)$ に当てると、$\lvert N(x)\cap Y\rvert\ge(d(X,Y)-\varepsilon)\lvert Y\rvert$ と $\lvert N(x)\cap Z\rvert\ge(d(X,Z)-\varepsilon)\lvert Z\rvert$ の両方を満たす $x\in X$ の集合 $X'$ は $\lvert X'\rvert>(1-2\varepsilon)\lvert X\rvert$ を満たす。
$x\in X'$ を固定し、$N_Y:=N(x)\cap Y$、$N_Z:=N(x)\cap Z$ とおく。密度の仮定から $\lvert N_Y\rvert\ge(d(X,Y)-\varepsilon)\lvert Y\rvert\ge\varepsilon\lvert Y\rvert$、同じく $\lvert N_Z\rvert\ge\varepsilon\lvert Z\rvert$ なので、$(Y,Z)$ の ε-正則性から $d(N_Y,N_Z)\ge d(Y,Z)-\varepsilon$ である。よって
$$
e(N_Y,N_Z)\ge\bigl(d(Y,Z)-\varepsilon\bigr)\lvert N_Y\rvert\lvert N_Z\rvert\ge\bigl(d(X,Y)-\varepsilon\bigr)\bigl(d(X,Z)-\varepsilon\bigr)\bigl(d(Y,Z)-\varepsilon\bigr)\lvert Y\rvert\lvert Z\rvert
$$
である。$e(N_Y,N_Z)$ は、$x$ を第 1 成分とする左辺の組 $(x,y,z)$ の個数以下である。$x\in X'$ について足し、$\lvert X'\rvert>(1-2\varepsilon)\lvert X\rvert$ を使えばよい。$\square$
左辺の組 $(x,y,z)$ の 3 点は相異なる（ループがないので）。$X,Y,Z$ が互いに交わらなければ、左辺は 1 点ずつを $X,Y,Z$ にもつ三角形の個数そのものである。交わる場合も、1 つの三角形は左辺で高々 $3!=6$ 回数えられる。
例と反例
次の表は、thm-reg-counting の仮定を 1 つずつ外した例である。どちらも $\varepsilon=1/4$、$t\ge1$ とし、$X,Y,Z$ は互いに交わらない $2t$ 点の集合で、辺は $X\cup Y\cup Z$ の上にだけある。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 3 つの対が ε-正則 | $X=X_1\cup X_2$ などと $t$ 点ずつに分け、$X_1\times Y_1$、$X_2\times Y_2$、$Y_1\times Z_2$、$Y_2\times Z_1$、$X_1\times Z_1$、$X_2\times Z_2$ の組をすべて結ぶ | 3 つの密度はどれも $1/2=2\varepsilon$ で右辺は $t^3/16>0$ だが、三角形はない |
| 3 つの密度が $2\varepsilon$ 以上 | $Y$ と $Z$ のあいだだけをすべて結ぶ | 3 つの対は ε-正則（完全な対か空の対）で右辺は $\frac12\cdot\frac1{16}\cdot\frac34\cdot8t^3>0$ だが、三角形はない |
確かめ：1 行目で $x\in X_1$ なら、$x$ と隣接する $Y$ の点は $Y_1$、$Z$ の点は $Z_1$ にあるが、$Y_1$ と $Z_1$ のあいだに辺はないので三角形はない。$x\in X_2$ でも同じである。$A=X_1$、$B=Y_2$ は $\lvert A\rvert=\lvert X\rvert/2\ge\varepsilon\lvert X\rvert$、$\lvert B\rvert\ge\varepsilon\lvert Y\rvert$、$d(A,B)=0$ を満たし、$\lvert0-1/2\rvert>\varepsilon$ なので $(X,Y)$ は ε-正則でない。2 行目では $d(X,Y)-\varepsilon=d(X,Z)-\varepsilon=-1/4$ が 2 つ負になるので右辺が正になる。条件 $d\ge2\varepsilon$ は、各因数 $d-\varepsilon$ が $\varepsilon$ 以上で、prf-reg-counting で近傍が十分大きくなることを保証している。
正則性の方法と応用
正則性補題の典型的な使い方は次の 3 段である（Zha23 Remark 2.3.2、p. 65）。
- 正則性補題でグラフの頂点を分割する。
- ε-正則でない対、密度の小さい対、小さすぎる部分に関わる辺を取り除く。取り除く辺は $\varepsilon n^2$ 本程度で少ない。
- 残ったグラフで、数え上げ補題を使って部分グラフを数える。
この 3 段で得られる代表的な結果が 三角形除去補題 である：三角形が $o(n^3)$ 個しかない $n$ 頂点のグラフは、$o(n^2)$ 本の辺を除くと三角形をなくせる。その系として、3 項の等差数列を含まない $\{1,\dots,N\}$ の部分集合の要素数が $o(N)$ であること（Szemerédiの定理 の $k=3$ の場合）が得られる。三角形を一般のグラフ $H$ に替えた除去補題（Zha23 Theorem 2.6.5、p. 75）や、一様ハイパーグラフの正則性と除去補題（同 Theorem 2.10.1、p. 86。Rödl らと Gowers による）もあり、後者からは一般の $k$ についての Szemerédiの定理 が導かれる（この記事では証明しない）。
部分の個数が塔の形で増えるため、正則性の方法で得られる評価は定量的には非常に弱い。たとえば上の 3 項の等差数列の要素数の上界は、この方法では $N/(\log^*N)^c$（$\log^*N$ は $N$ を $1$ 以下にするのに要る対数の反復回数、$c>0$ は定数）の形にとどまり（Zha23 Remark 2.4.5、p. 70）、Szemerédiの定理 の記事で Fourier 解析によって示す $N/\log\log N$ よりはるかに弱い。
関連項目
- 前提: グラフ, 部分グラフ, Cauchy–Schwarzの不等式, 分散
- 応用: 三角形除去補題, Szemerédiの定理
- 関連: 極値グラフ理論, Turánの定理, Mantelの定理, 累乗の塔
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
