↓メインコンテンツへスキップ
組合せ論、楽しい！

【月刊組合せ論 Natori】グラフ除去補題【2025 年 7 月号】

·
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はグラフ除去補題を紹介します。

グラフ除去補題とは
#

グラフ HH の頂点数を v(H)v(H) とします。グラフ除去補題とは次の定理です。

定理: 任意のグラフ HH および任意の ε>0\varepsilon>0 に対して、ある δ=δ(H,ε)>0\delta=\delta(H,\varepsilon)>0 が存在して、nn 頂点グラフ GG であって部分グラフとして現れる HH の個数が高々 δnv(H)\delta n^{v(H)} であるものは辺を高々 εn2\varepsilon n^2 個削除することで HH をなくすことができる。

特に HH が三角形 (3 頂点からなるサイクル) のときは、三角形除去補題と呼ばれます。

定理: 任意の ε>0\varepsilon>0 に対して、ある δ=δ(ε)>0\delta=\delta(\varepsilon)>0 が存在して、nn 頂点グラフ GG であって部分グラフとして現れる三角形の個数が高々 δn3\delta n^3 であるものは辺を高々 εn2\varepsilon n^2 個削除することで三角形をなくすことができる。

Roth の定理
#

三角形除去補題の有名な応用として Roth の定理があります。

定理: A⊂{1,2,…,N}A\subset \{1,2,\ldots,N\} が長さ 3 の等差数列を含まないならば、∣A∣=o(N)|A|=o(N) である。

整数論とグラフ理論が結びつくのは面白いですね。

Roth の定理は長さ 3 の等差数列に関する定理ですが、長さを 3 以上の整数に一般化することができ、セメレディの定理と呼ばれています。セメレディの定理はハイパーグラフ除去補題を用いて証明することができます。

素数からなる等差数列に関する有名なグリーン・タオの定理がありますが、セメレディの定理から導くことはできません (素数は密度が 0 なので)。しかしこの記事で述べる概念が大いに関わってきます。

正則化補題とグラフ数え上げ補題
#

グラフ除去補題を証明するカギとなるのは次の 2 つの補題です。

  • セメレディの正則化補題
  • グラフ数え上げ補題

正則化補題は大雑把にいえば、大きなグラフは頂点集合をいくつかのパーツに分けることで、どの 2 つのパーツの間もランダムっぽくすることができるという命題です。ランダムっぽいという概念を定式化したものが ε\varepsilon 正則分割です。ざっくり見ていきましょう。

立川志の輔さんと秋山仁さんの有名なエピソードで、大きな鍋に入った味噌汁の味見は少し飲むだけでできるが、統計も同じだといった趣旨のものがあります。よく混ざっていれば味の濃さは一定なので、少しでよいということですね。ランダムグラフでも、濃さが一定であることを期待します。

U,WU,W を頂点からなる集合、A⊆U,B⊆WA\subseteq U, B\subseteq W を部分集合とします。A,BA,B 間の濃さ、すなわち辺密度 d(A,B)d(A,B) を A,BA,B 間の辺の個数を要素数の積 ∣A∣×∣B∣|A|\times |B| で割った余りとします。これが全体の辺密度 d(U,W)d(U,W) とあまり変わらないことを期待します。もちろん A,BA,B を一点集合にしてしまうと密度が 0 または 1 になってしまうので、A,BA,B はある程度大きくしないといけません。

いよいよ定義に移ります。(U,W)(U,W) が ε\varepsilon 正則とは、∣A∣≥ε∣U∣,∣B∣≥ε∣W∣|A|\ge \varepsilon |U|, |B|\ge \varepsilon |W| をみたす任意の部分集合 A,BA,B に対して ∣d(A,B)−d(U,W)∣≤ε|d(A,B)-d(U,W)|\le \varepsilon をみたすことです。

∣A∣≥ε∣U∣,∣B∣≥ε∣W∣|A|\ge \varepsilon |U|, |B|\ge \varepsilon |W| に現れる ε\varepsilon は A,BA,B があまり小さくならないようにするために用いられ、∣d(A,B)−d(U,W)∣≤ε|d(A,B)-d(U,W)|\le \varepsilon に現れる ε\varepsilon は辺密度の差が小さいことを表すために用いられます。2 つの役割は別ですが、別の記号を用いるメリットがあまりないので同じ記号を用いています。

頂点集合の分割 V=V1⊔V2⊔⋯⊔VMV=V_1\sqcup V_2\sqcup\cdots\sqcup V_M において、各 (Vi,Vj)(V_i,V_j) が ε\varepsilon 正則という状況を考えたいですが、この定義ではうまくいかないことが知られています。そこで一部は ε\varepsilon 正則でないことを許容します。それを正確に定義したものが ε\varepsilon 正則分割です。この記事では用いないので正確な定義は紹介しません。

以上の準備のもとでセメレディの正則化補題を述べることができます。

定理 (セメレディの正則化補題): 任意の ε>0\varepsilon>0 に対して、ある MM が存在して、任意のグラフは高々 MM 個のパーツからなる ε\varepsilon 正則分割をもつ。

もう一つのカギであるグラフ数え上げ補題を紹介します。話を簡単にするため三角形数え上げ補題を紹介します。

定理 (三角形数え上げ補題): X,Y,ZX,Y,Z を頂点集合であって (X,Y),(X,Z),(Y,Z)(X,Y),(X,Z),(Y,Z) が ε\varepsilon 正則であるものとする。d(X,Y),d(X,Z),d(Y,Z)≥2εd(X,Y),d(X,Z),d(Y,Z)\ge 2\varepsilon ならば

∣{(x,y,z)∈X×Y×Z∣xyz は三角形}∣≥(1−2ε)(d(X,Y)−ε)(d(X,Z)−ε)(d(Y,Z)−ε)∣X∣∣Y∣∣Z∣ \begin{gather*} |\{(x,y,z)\in X\times Y\times Z \mid xyz \text{ は三角形}\}| \\ \ge (1-2\varepsilon)(d(X,Y)-\varepsilon)(d(X,Z)-\varepsilon)(d(Y,Z)-\varepsilon)|X||Y||Z| \end{gather*}

が成り立つ。

グラフ除去補題の証明の流れは次のようになります。

  • 正則化補題で頂点集合を分割する
  • 性質の悪い辺を削除する（高々 εn2\varepsilon n^2 個）
  • HH が存在したと仮定して、グラフ数え上げ補題で HH の個数が δnv(H)\delta n^{v(H)} を超えることを示す

bound
#

よく数学者は存在することだけ証明して満足すると言われがちですが、そうでない人もいます。

グラフ除去補題において δ\delta が HH や ε\varepsilon にどう依存するかを調べる研究も行われています。

グラフ除去補題は正則化補題とグラフ数え上げ補題を用いて証明されていますが、正則化補題において次の結果が Gowers によって示されました。

ある c>0c>0 が存在して、十分小さな任意の ε>0\varepsilon>0 に対して、パーツの数が tower(⌈ε−c⌉)\mathrm{tower}(\lceil\varepsilon^{-c}\rceil) 以下であるような ε\varepsilon 正則分割をもたないようなグラフが存在する。

ここで tower(k)=22⋯2\mathrm{tower}(k)=2^{2^{\cdots^2}} (2 が kk 個) なので、ε\varepsilon が小さくなるとパーツ数はとてつもなく大きくなることがわかります。この結果の簡単な証明は Moshkovitz と Shapira の論文にあります。

  • Moshkovitz, Guy; Shapira, Asaf. A short proof of Gowers’ lower bound for the regularity lemma. Combinatorica 36, No. 2, 187-194 (2016).

さて、グラフ除去補題の証明では正則化補題を使うので、グラフ除去補題における δ\delta も似たような大きさになります：

δ−1=tower(ε−O(1)) \delta^{-1}=\mathrm{tower}(\varepsilon^{-O(1)})

ところが、Fox によるグラフ除去補題の別証明では δ\delta を次のようにとれることが示されました：

δ−1=tower(O(log⁡(ε−1))) \delta^{-1}=\mathrm{tower}(O(\log(\varepsilon^{-1})))

これはずっと小さい値です。この事実は、セメレディの正則化補題はグラフ除去補題を証明するには強すぎる可能性を示唆しています。

弱い正則化補題
#

正則化補題よりも弱い命題はいくつか知られています。

  • Frieze-Kannan の弱正則化補題
  • Duke-Lefman-Rödl のシリンダー正則化補題

Fox の証明では Frieze-Kannan の弱正則化補題が用いられていますが、上で述べたグラフ除去補題の証明とは異なる流れです。

ここでは次の命題を紹介します。Alon, Fischer, Krivelevich, Szegedy の定理で、シリンダー正則化補題の亜種だそうです。

定理 (★): 任意の ε>0\varepsilon>0 および hh に対して、ある S=S(ε,h)S=S(\varepsilon,h) が存在して、任意のグラフ GG は equipartition {V1,…,Vk}\{V_1,\ldots,V_k\} および部分集合 Wi⊆Vi (i=1,…,k)W_i\subseteq V_i \ (i=1,\ldots,k) であって次をみたすものをもつ。

  • ∑1≤i<j≤k∣d(Vi,Vj)−d(Wi,Wj)∣≤εk2\sum_{1\le i<j\le k}|d(V_i,V_j)-d(W_i,W_j)|\le \varepsilon k^2
  • すべての組 (Wi,Wj)(W_i,W_j) は εh\varepsilon^h 正則
  • ∣Wi∣≥∣V(G)∣/S|W_i|\ge |V(G)|/S

ここで equipartition とは ∣∣Vi∣−∣Vj∣∣≤1||V_i|-|V_j||\le 1 となる分割のことで、要するに均等な分割です。この記事では話を簡単にするために、各 ViV_i の要素数はちょうど ∣V(G)∣k\frac{|V(G)|}{k} とします。

S(ε,h)S(\varepsilon,h) については次のような評価が知られています。

GG の辺密度が O(ε)O(\varepsilon) ならば、S(ε,h)≤tower(O(log⁡(ε−1)))S(\varepsilon,h)\le \mathrm{tower}(O(\log(\varepsilon^{-1})))

残念ながら一般のグラフ GG ではこの結果は得られません。ですが、Fox の結果を得るには辺密度が小さいグラフのみを考えればよいのです。

証明
#

以上の話をまとめて、グラフ除去補題および Fox による評価を証明します。

話を簡単にするために、三角形除去補題のみ証明します。一般のグラフ除去補題の証明は原論文をあたってください。

正則化補題と評価
#

定理 (★)、およびそこに現れる SS の評価（すなわち、GG の辺密度が O(ε)O(\varepsilon) ならば、S(ε,h)≤tower(O(log⁡(ε−1)))S(\varepsilon,h)\le \mathrm{tower}(O(\log(\varepsilon^{-1})))）については、Sapir, Shapira の論文を読んでください。（注意点として、論文では εh\varepsilon^h 正則の部分が εh4h\frac{\varepsilon^h}{4h} 正則になっています）

辺密度 O(ε)O(\varepsilon) のグラフに対する三角形除去補題
#

GG を nn 頂点のグラフであって、辺密度 O(ε)O(\varepsilon)、三角形をなくすために少なくとも εn2\varepsilon n^2 辺の削除が必要であるとします。

定理 (★) を ε2\frac{\varepsilon}{2} として用いることで、equipartition {V1,…,Vk}\{V_1,\ldots,V_k\} および部分集合 Wi⊆Vi (i=1,…,k)W_i\subseteq V_i \ (i=1,\ldots,k) であって次をみたすものをとることができます。

  • ∑1≤i<j≤k∣d(Vi,Vj)−d(Wi,Wj)∣≤ε2k2\sum_{1\le i<j\le k}|d(V_i,V_j)-d(W_i,W_j)|\le \frac{\varepsilon}{2} k^2
  • すべての組 (Wi,Wj)(W_i,W_j) は ε38\frac{\varepsilon^3}{8} 正則
  • ∣Wi∣≥∣V(G)∣/S|W_i|\ge |V(G)|/S

d(Wi,Wj)≤ε2d(W_i,W_j)\le \frac{\varepsilon}{2} をみたすような Vi,VjV_i,V_j 間の辺を削除します。削除する辺の数は

∑d(Vi,Vj)∣Vi∣∣Vj∣=n2k2∑d(Vi,Vj)≤n2k2(∑∣d(Vi,Vj)−d(Wi,Wj)∣+∑d(Wi,Wj))<n2k2(ε2k2+ε2k2)=εn2 \begin{align*} \sum d(V_i,V_j)|V_i||V_j| &= \frac{n^2}{k^2}\sum d(V_i,V_j) \\ &\le \frac{n^2}{k^2}\left(\sum|d(V_i,V_j)-d(W_i,W_j)|+\sum d(W_i,W_j)\right) \\ &< \frac{n^2}{k^2}\left(\frac{\varepsilon}{2}k^2+\frac{\varepsilon}{2}k^2\right) \\ &= \varepsilon n^2 \end{align*}

ここで和は d(Wi,Wj)≤ε2d(W_i,W_j)\le \frac{\varepsilon}{2} をみたす i≠ji\ne j 上をわたります。

削除後のグラフに三角形が存在します。その頂点が Vi,Vj,VkV_i,V_j,V_k 上にあるとすると

d(Wi,Wj),d(Wi,Wk),d(Wj,Wk)≥ε2≥ε34 d(W_i,W_j), d(W_i,W_k), d(W_j,W_k)\ge \frac{\varepsilon}{2}\ge \frac{\varepsilon^3}{4}

となります。三角形数え上げ補題を適用すると、三角形の個数は

≥(1−ε34)(ε38)3n3S3 \ge \left(1-\frac{\varepsilon^3}{4}\right)\left(\frac{\varepsilon^3}{8}\right)^3\frac{n^3}{S^3}

となります。辺密度が O(ε)O(\varepsilon) より S≤tower(O(log⁡(ε−1)))S\le \mathrm{tower}(O(\log(\varepsilon^{-1}))) が成り立つので、三角形の個数は

≥n3/tower(O(log⁡(ε−1))) \ge n^3/\mathrm{tower}(O(\log(\varepsilon^{-1})))

となり、Fox の評価が得られました。

一般のグラフに対する三角形除去補題
#

GG を三角形をなくすために辺を εn2\varepsilon n^2 回以上削除しなければならないグラフとします。辺を共有しない三角形を最大で mm 個選べるとします。mm 個の三角形の三辺をすべて削除すれば GG から三角形がなくなるので、3m≥εn23m\ge \varepsilon n^2 となります。εn2/3\varepsilon n^2/3 個の三角形からなる部分グラフを G′G' とします。すると辺密度が ε\varepsilon で、三角形をなくすために εn2/3\varepsilon n^2/3 回以上辺を削除する必要があります。よって上述の三角形除去補題が ε/3\varepsilon/3 に対して適用可能です。G′G' に現れる三角形は GG にも現れることを用いると、一般の場合の証明ができます。

おわりに
#

セメレディの正則化補題はこの分野の中心的存在なので、別の記事でも扱うかもしれません。その際はより深掘りしたいと思っています。

しばらく更新をおやすみしていた月刊組合せ論 Natori ですが、今月号から連載を再開しようと思います。応援のほどよろしくお願いします！

参考文献
#

  • Sapir, Shachar; Shapira, Asaf. The induced removal lemma in sparse graphs. Comb. Probab. Comput. 29, No. 1, 153-162 (2020).
  • Shapira, Asaf. Local-vs-global combinatorics. ICM 2022.
  • Zhao, Yufei. Graph theory and additive combinatorics. Exploring structure and randomness. Cambridge University Press (2023).