数え上げ補題

この記事で扱う計数補題は、組合せ論とグラフ理論における命題である。最初の補題は、グラフ 内の頂点の部分集合の -正則ペアから情報を抽出し、グラフ全体のパターンを保証するものである。より明確に言えば、これらのパターンはにおける特定のグラフのコピー数に対応する。2つ目の計数補題は、グラフオン空間における同様だがより一般的な概念であり、2つのグラフ間のカット距離のスカラーが、それらの間の準同型密度と相関している。 ${\displaystyle \epsilon }$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

グラフ埋め込み版の計数補題

グラフ 内に頂点のサブセットの -正規ペアがある場合は、次のように解釈できます。密度 の二部グラフ は、すべてのエッジが確率 で出現し、多少の誤差があるランダム二部グラフに近いものです。 ${\displaystyle \epsilon }$ ${\displaystyle U,V}$ ${\displaystyle G}$ ${\displaystyle (U,V)}$ ${\displaystyle d(U,V)}$ ${\displaystyle d(U,V)}$ ${\displaystyle \epsilon }$

複数の頂点クラスターがあり、これらのクラスター間のペアの一部が -正則である場合、小さなパターン、つまり局所的なパターンの数は、ランダムグラフにおけるそのようなパターンの数とほぼ等しくなると予想されます。これらの小さなパターンとは、例えば、におけるいくつかの のグラフ埋め込みの数、より具体的には、各頂点クラスターから1つの頂点を取ることによって形成されるにおけるのコピーの数などです。 ${\displaystyle \gamma }$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

上記の直感は正しいが、定理を完全に記述するためには、いくつかの重要な条件を満たす必要がある。例えば、ペアワイズ密度は少なくとも、クラスターサイズは少なくとも、 である。これらの詳細をより注意深く考慮すると、グラフ計数補題の記述は次のようになる。${\displaystyle \varepsilon }$ ${\displaystyle \gamma ^{-1}}$ ${\displaystyle \gamma \leq \varepsilon ^{h}/4h}$

定理の記述

が頂点と辺を持つグラフで、が（必ずしも互いに素ではない）頂点サブセットを持つグラフで、ペアのすべての辺に対して が密度と を持つ-正則グラフである 場合、にはの頂点のコピーを持つ のコピーが少なくとも多数含まれます。${\displaystyle H}$ ${\displaystyle 1,\cdots ,h}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle W_{1},\cdots ,W_{h}}$ ${\displaystyle |W_{i}|\geq \gamma ^{-1}}$ ${\displaystyle i=1,\ldots ,h}$ ${\displaystyle (i,j)}$ ${\displaystyle H}$ ${\displaystyle (W_{i},W_{j})}$ ${\displaystyle \gamma }$ ${\displaystyle d(W_{i},W_{j})>\varepsilon }$ ${\displaystyle \gamma \leq \varepsilon ^{h}/4h}$ ${\displaystyle G}$ ${\displaystyle 2^{-h}\varepsilon ^{m}|W_{1}|\cdot \ldots \cdot |W_{h}|}$ ${\displaystyle H}$ ${\displaystyle i}$ ${\displaystyle W_{i}}$

この定理は三角形の数え上げの補題を一般化したものであって、次のようになる。${\displaystyle H=K_{3}}$

三角形の数え上げの補題

を頂点とするグラフとし、その部分集合が対ごとに-正則 であるとし、辺密度がすべて少なくとも であるとする。このとき、 が三角形を形成するような三つ組の数は少なくとも である。${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle X,Y,Z}$ ${\displaystyle V(G)}$ ${\displaystyle \epsilon }$ ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$ ${\displaystyle 2\epsilon }$ ${\displaystyle (x,y,z)\in X\times Y\times Z}$ ${\displaystyle x,y,z}$ ${\displaystyle G}$ $${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|X||Y||Z|.}$$

三角形の数え上げ補題の証明:

は正則な対なので、の頂点のうち 個未満の頂点は 個未満の隣接頂点を持ちます。そうでない場合、 の頂点集合は の隣接頂点と共に の不規則性を示し、矛盾が生じます。直感的に言えば、 の頂点のうち、 において小さい次数を持つ頂点はそれほど多くないと言えます。 ${\displaystyle (X,Y)}$ ${\displaystyle \varepsilon |X|}$ ${\displaystyle X}$ ${\displaystyle (d_{XY}-\varepsilon )|Y|}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$

のペアにおいても同様の議論が成り立ち、の頂点のうち 個未満の頂点は 個未満の隣接頂点を持ちます。 と のこれら2つの部分集合を結合し、それらの補集合をとると、のサイズが少なくとも 個の部分集合が得られ、この部分集合ではすべての頂点は に少なくとも 個の隣接頂点を持ち、 に少なくとも個の隣接頂点を持ちます。 ${\displaystyle (X,Z)}$ ${\displaystyle \varepsilon |X|}$ ${\displaystyle X}$ ${\displaystyle (d_{XZ}-\varepsilon )|Z|}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle X'\subseteq X}$ ${\displaystyle (1-2\varepsilon )|X|}$ ${\displaystyle x\in X'}$ ${\displaystyle (d_{XY}-\varepsilon )|Y|}$ ${\displaystyle Y}$ ${\displaystyle (d_{XZ}-\varepsilon )|Z|}$ ${\displaystyle Z}$

また、 であり、 が-正則ペアであることもわかっています。したがって、におけるの近傍とにおけるの近傍の間の密度は少なくとも です。これは、正則性によりとの間の実際の密度に -近いためです。 ${\displaystyle d_{XY},d_{XZ}\geq 2\varepsilon }$ ${\displaystyle (Y,Z)}$ ${\displaystyle \varepsilon }$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle Z}$ ${\displaystyle (d_{YZ}-\varepsilon )}$ ${\displaystyle \varepsilon }$ ${\displaystyle Y}$ ${\displaystyle Z}$

まとめると、これらの少なくとも個の頂点それぞれについて、におけるの近傍とにおけるの近傍の間には少なくとも個の辺の選択肢があります。そこからこの証明を結論付けることができます。 ${\displaystyle (1-2\varepsilon )|X|}$ ${\displaystyle x\in X'}$ ${\displaystyle (d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|Y||Z|}$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle Z}$

グラフ計数補題の証明のアイデア:グラフ計数補題の一般的な証明は、貪欲な埋め込み戦略を通じてこの議論を拡張します。つまり、 の頂点は、次の頂点を埋め込むのに十分な大きさの頂点の集合を保持できるように、正則性条件を使用して、グラフに1つずつ埋め込まれます。^[1]${\displaystyle H}$

グラフン版の計数補題

グラフオンの空間は、距離空間の構造を持つ。ここで、距離はカット距離である。次の補題は、がコンパクト距離空間であることを証明するための重要なステップである。直感的には、グラフ に対して、2つのグラフオンのこのグラフに関する準同型密度は、グラフオンがカット距離に関して近い場合、近くなければならない（この境界は辺の数に依存する）ということを述べている。 ${\displaystyle {\tilde {\mathcal {W}}}_{0}}$ ${\displaystyle \delta _{\Box }}$ ${\displaystyle ({\tilde {\mathcal {W}}}_{0},\delta _{\Box })}$ ${\displaystyle F}$ ${\displaystyle F}$

定義（カットノルム）。

のカットノルムは と定義されます。ここで、 と は測定可能な集合です。 ${\displaystyle W:[0,1]^{2}\to \mathbb {R} }$ ${\displaystyle \|W\|_{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S\times T}W\right|}$ ${\displaystyle S}$ ${\displaystyle T}$

定義（カット距離）。

カット距離は として定義されます。ここで は測度保存一対一 を表します。${\displaystyle \delta _{\square }(U,W)=\inf _{\phi }||U-W^{\phi }||_{\square }}$ ${\displaystyle W^{\phi }(x,y)}$ ${\displaystyle W(\phi (x),\phi (y))}$ ${\displaystyle \phi }$

グラフンの数え上げ補題

グラフオンおよびグラフ については、 が成り立ちます。ここで、 はグラフ の辺の数を表します。${\displaystyle W,U}$ ${\displaystyle F}$ ${\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\delta _{\square }(W,U)}$ ${\displaystyle |E(F)|}$ ${\displaystyle F}$

グラフオン数え上げ補題の証明:

実際に、上記を考慮して、右辺の式に の代わりに因子を持たせ、測度保存の全一対一の最小値を取ることで、目的の結果が得られる 。$${\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\|W-U\|_{\square }.}$$ ${\displaystyle \|W-U^{\phi }\|_{\Box }}$ ${\displaystyle \|W-U\|_{\Box }}$ ${\displaystyle \phi }$

ステップ1：再定式化。定義により次の等式の左辺となるカットノルムの再定式化を証明する。右辺の上限は、測定可能な関数との間で取られる。${\displaystyle u}$ ${\displaystyle v}$ $${\displaystyle \sup _{S,T\subseteq [0,1]}\left|\int _{S\times T}W\right|=\sup _{u,v:[0,1]\rightarrow [0,1]}\left|\int _{[0,1]^{2}}W(x,y)u(x)v(y)dxdy\right|.}$$

上記が成り立つ理由は以下の通りです。 および をとると、左辺は右辺より小さいか等しいことがわかります。右辺が左辺より小さいか等しいのは、 における積分関数の双線型性と、 またはで値をとった場合に極値が得られるという事実によるものです。 ${\displaystyle u=\mathbb {1} _{S}}$ ${\displaystyle u=\mathbb {1} _{T}}$ ${\displaystyle u,v}$ ${\displaystyle u,v}$ ${\displaystyle 0}$ ${\displaystyle 1}$

ステップ2: の証明。${\displaystyle F=K_{3}}$ の場合、次のことが分かります。 ${\displaystyle F=K_{3}}$

$${\displaystyle {\begin{aligned}t(K_{3},W)-t(K_{3},U)&=\int _{[0,1]^{3}}((W(x,y)W(x,z)W(y,z)-U(x,y)U(x,z)U(y,z))dxdydz\\&=\int _{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\\&\qquad +\int _{[0,1]^{3}}U(x,y)(W-U)(x,z)W(y,z)dxdydz\\&\qquad +\int _{[0,1]^{3}}U(x,y)U(x,z)(W-U)(y,z)dxdydz.\end{aligned}}}$$

ステップ1では、固定値に対して${\displaystyle z}$

${\displaystyle \left|\int _{[0,1]^{2}}(W-U)(x,y)W(x,z)W(y,z)dxdy\right|\leq \|W-U\|_{\square }}$

したがって、全体を積分すると 、${\displaystyle z\in [0,1]}$

${\displaystyle \left|\int _{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\right|\leq \|W-U\|_{\square }}$

この上限を3つの被加数それぞれに適用すると、全体の和は で制限されることがわかります。 ステップ3：一般的なケース。一般的なグラフ の場合、すべてをより便利にするために、次の補題が必要です。${\displaystyle 3\|W-U\|_{\square }}$ ${\displaystyle F}$

補題。

次の式が成り立ちます。$${\displaystyle a_{1}a_{2}\cdots a_{n}-b_{1}b_{2}\cdots b_{n}=(a_{1}-b_{1})a_{2}\cdots a_{n}+b_{1}(a_{2}-b_{2})\cdots a_{n}+\cdots b_{1}b_{2}\cdots (a_{n}-b_{n}).}$$

上記の補題は右辺の直接的な展開から導かれる。すると、ノルムの三角不等式により、次の式が得られる。$${\displaystyle {\begin{aligned}\left|t(F,W)-t(F,U)\right|&=\left|\int \left(\prod _{u_{i}v_{i}\in E(F)}W(u_{i},v_{i})-\prod _{u_{i}v_{i}\in E(F)}U(u_{i},v_{i})\right)\prod _{v\in V}dv\right|\\&\leq \sum _{i=1}^{|E(F)|}\left|\int \left(\ \prod _{j=1}^{i-1}U(u_{j},v_{j})(W(u_{i},v_{i})-U(u_{i},v_{i}))\prod _{k=i+1}^{|E(F)|}W(u_{k},v_{k})\right)\prod _{v\in V}dv\right|.\end{aligned}}}$$

ここで、を除くすべての変数を固定し、各- 番目の項について を固定すると、和の各絶対値項はカットノルムによって制限され、全体として が成立することを意味します。これで証明は終了です。 ${\displaystyle \|W-U\|_{\square }}$ ${\displaystyle u_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle i}$ ${\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\ \delta _{\square }(W,U)}$

参照

• グラフ削除補題

参考文献

1. Conlon, Fox, David, Jacob. 「グラフ除去補題」(PDF)。David Conlonのウェブページ。2013年10月1日時点のオリジナルからアーカイブ(PDF) 。