コンテナ方式

（ハイパーグラフ）コンテナ法は、所定の一連のローカル制約を持つ離散オブジェクトの族に関する典型的な構造を特徴付けたり、極限的な質問に答えたりするのに役立つ強力なツールです。このような疑問は、極限グラフ理論、加法組合せ論、離散幾何学、符号理論、ラムゼー理論で自然に生じ、関連分野の最も古典的な問題のいくつかを含みます。

これらの問題は、次の形式の質問として表現できます。辺集合Eを持つ有限頂点集合V上のハイパーグラフ H (つまり、いくつかのサイズ制約を持つVのサブセットのコレクション) が与えられた場合、 Hの独立集合(つまり、 Eの要素を含まないVのサブセット)については何が言えるでしょうか。ハイパーグラフ コンテナの補題は、このような質問に取り組む方法を提供します。

極値グラフ理論の基本的な問題の 1 つは、1907 年の Mantel と1940 年代のTuránの研究にまで遡るもので、サブグラフとして固定された禁制 Hのコピーを含まないグラフを特徴付けることです。別の領域では、加法組合せ論における動機づけとなる問題の 1 つは、 k項等差数列を含まない整数の集合がどの程度の大きさになるかを理解することであり、このサイズの上限はRoth ( ) とSzemerédi (一般的なk )によって与えられています。 ${\displaystyle k=3}$

コンテナ法（グラフ内）は、1980年にクライトマンとウィンストンによって最初に開拓され、格子の数^[1]と4閉路のないグラフの数を制限しました^[2] 。コンテナスタイルの補題は、さまざまなコンテキストで複数の数学者によって独立に開発されました。特にサポジェンコは、2002年から2003年にこのアプローチを最初に使用して、正則グラフの独立集合^[3] 、アーベル群の和のない集合^[4]を列挙し、その他のさまざまな列挙問題を研究しました^[5]。

これらのアイデアをハイパーグラフコンテナ補題に一般化する手法は、2015年にサクストンとトーマスン^[6]とバログ、モリス、サモティ^[7]によって独立に考案され、さまざまな関連研究に触発された。

組合せ論における多くの問題は、グラフやハイパーグラフ内の独立集合に関する問題として言い換えることができます。たとえば、k項等差数列を持たないで表す整数1からnのサブセットを理解したいとします。これらの集合は、 k一様ハイパーグラフ内の独立集合とまったく同じです。ここで、E は内のすべてのk項等差数列の集合です。 ${\displaystyle [n]}$${\displaystyle H=(\{1,2,\ldots ,n\},E)}$${\displaystyle \{1,2,\ldots ,n\}}$

上記の例（および他の多くの例）では、ハイパーグラフHに関して提起される問題には通常 2 つの自然なクラスがあります。

• Hにおける最大独立集合のサイズはどれくらいですか? Hにおける最大サイズの独立集合のコレクションはどのように見えるでしょうか?
• Hには独立集合がいくつありますか? Hの「典型的な」独立集合はどのようなものですか?

これらの問題は単純な観察によって結びついています。Hの最大独立集合のサイズを とし、独立集合が であるとします。すると、 ${\displaystyle \alpha (H)}$${\displaystyle H}$${\displaystyle i(H)}$

${\displaystyle 2^{\alpha (H)}\leq i(H)\leq \sum _{r=0}^{\alpha (H)}{|V(H)| \choose r},}$

ここで、下限は最大独立集合のすべてのサブセットを取ることによって得られます。 が非常に大きく、ハイパーグラフの頂点の数に近い場合を除き、これらの境界は互いに比較的離れています。ただし、組み合わせ問題で自然に生じる多くのハイパーグラフでは、下限が真の値に近いと信じる理由があります。したがって、主な目標はi(H)の上限を改善することです。 ${\displaystyle \alpha (H)}$

ハイパーグラフ コンテナ補題は、ハイパーグラフ内の独立集合の族の構造とサイズを理解するための強力なアプローチを提供します。 本質的に、ハイパーグラフ コンテナ メソッドを使用すると、ハイパーグラフから、次のプロパティを満たす頂点のサブセットである コンテナのコレクションを抽出できます。

• コンテナはそれほど多くありません。
• 各コンテナーは、最大の独立セットよりもそれほど大きくありません。
• 各コンテナにはエッジがほとんどありません。
• ハイパーグラフ内のすべての独立集合は、何らかのコンテナーに完全に含まれます。

コンテナという名前は、この最後の条件を暗示しています。このようなコンテナは、独立集合のファミリ (コンテナのサブセット) を特徴付けたり、ハイパーグラフの独立集合を列挙したり (コンテナの可能なすべてのサブセットを単純に考慮することによって) するための効果的なアプローチを提供することがよくあります。

ハイパーグラフ コンテナ補題は、上記のコンテナ分解を 2 つの部分で実現します。決定論的関数fを構築します。次に、ハイパーグラフHの各独立集合Iから、という特性を持つ、フィンガープリントと呼ばれる比較的小さな頂点の集合を抽出するアルゴリズムを提供します。次に、コンテナは上記のプロセスで発生する集合の集合であり、フィンガープリントのサイズが小さいため、このようなコンテナ集合の数を適切に制御できます。 ${\displaystyle S\subset I}$${\displaystyle S\subset I\subset S\cup f(S)}$${\displaystyle S\cup f(S)}$

まず、グラフ内の独立集合の数の強い上限を示す方法を説明します。この説明は、もともとKleitman-WinstonとSapozhenkoによって採用されたグラフコンテナ法に関するSamotij ^[8]の調査を基にしたものです。

以下のセクションでは次の表記を使用します。

• ${\displaystyle G=(V,E)}$は頂点上のグラフであり、頂点集合には（任意の）順序が与えられます。${\displaystyle |V|=n}$${\displaystyle \{v_{1},\ldots ,v_{n}\}}$
• をGの独立集合の集合(サイズ ) と します。をサイズrの独立集合の数とします。${\displaystyle \ell (G)}$${\displaystyle i(G):=|\ell (G)|}$${\displaystyle i(G,r)}$
• 頂点サブセットの最大次数順序は、誘導サブグラフ内の次数によってA内の頂点を順序付けすることです。${\displaystyle A\subset V}$ ${\displaystyle G[A]}$

次のアルゴリズムは、グラフ内の各独立集合に対して小さな「指紋」と、その指紋の決定論的関数を与えて、独立集合全体を含む大きすぎないサブセットを構築します。

グラフG、独立集合、正の整数を固定します。 ${\displaystyle I\in \ell (G)}$${\displaystyle q\leq |I|}$

1. 初期化: let 。${\displaystyle A=V(G),S=\emptyset }$
2. 繰り返し処理: ${\displaystyle s=1,2,\ldots ,q}$
   • 最大次数順序を構築する${\displaystyle A,\,(v_{1},\ldots v_{|A|})}$
   • （つまり、誘導部分グラフG[A]の最大次数を持つAの頂点）となる最小のインデックスを見つける。${\displaystyle j_{s}}$${\displaystyle v_{j_{s}}\in I}$
   • とします。ここで は頂点 の近傍です。${\displaystyle S\leftarrow S\cup \{v_{j_{s}}\},\,A\leftarrow A\backslash (\{v_{1},\ldots ,v_{j_{s}}\}\cup N(v_{j_{s}}))}$${\displaystyle N(v)}$${\displaystyle v}$
3. ベクトルと頂点セットを出力します。${\displaystyle (j_{1},\ldots,j_{q})}$${\displaystyle A\cap I}$

構築により、上記のアルゴリズムの出力は という特性を持ちます。ただし、 はによって完全に決定され、 の関数ではない頂点サブセットです。これを強調するために、 と書きます。また、上記のアルゴリズムの集合は、ベクトル からのみ再構築できることもわかります。 ${\displaystyle \{v_{j_{1}},\ldots ,v_{j_{q}}\}\subset I\subset \{v_{j_{1}},\ldots ,v_{j_{q}}\}\cup (A\cap I)}$${\displaystyle A\cap I}$${\displaystyle \{j_{1},\ldots ,j_{q}\}}$${\displaystyle I}$${\displaystyle A=A(j_{1},\ldots ,j_{q})}$${\displaystyle S=\{v_{j_{1}},\ldots ,v_{j_{q}}\}=S(j_{1},\ldots j_{q})}$${\displaystyle (j_{1},\ldots ,j_{q})}$

これは、 が指紋の適切な選択であり、コンテナの適切な選択である可能性があることを示唆している。より正確には、出力シーケンスの合計として、あるサイズの の独立集合の数を制限することができる。${\displaystyle S}$${\displaystyle S(j_{1},\ldots j_{q})\cup A(j_{1},\ldots ,j_{q})}$${\displaystyle G}$${\displaystyle r\geq q}$${\displaystyle (j_{1},\ldots j_{q})}$

${\displaystyle i(G,r)=\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})],r-q)\leq \sum _{(j_{s})}{A(j_{1},\ldots j_{q}) \choose r-q}}$、

ここで、グラフの独立集合の総数の上限を得るために 合計することができます。${\displaystyle r}$

${\displaystyle i(G)=\sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})])\leq \sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})}2^{|A(j_{1},\ldots j_{q})|}}$。

この上限を最小化しようとする場合、これら 2 つの項のバランスをとる/最小化する を選択する必要があります。この結果は、頂点を最大次数で順序付ける ( を最小化する) ことの価値を示しています。 ${\displaystyle q}$${\displaystyle |A(j_{1},\ldots j_{q})|}$

上記の不等式と観察は、ベクトル上の明示的な和から切り離された、より一般的な設定で述べることができます。 ${\displaystyle (j_{s})}$

補題1:および のグラフが与えられ、整数および実数がを満たすと仮定する。少なくとも の頂点上のすべての誘導サブグラフの辺密度が少なくとも であると仮定する。すると、すべての整数 に対して、 ${\displaystyle G}$${\displaystyle n}$${\displaystyle q}$${\displaystyle R,\beta \in [0,1]}$${\displaystyle R\geq e^{-\beta q}n}$${\displaystyle R}$${\displaystyle \beta }$${\displaystyle r\geq q}$

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}.}$

補題 2:を頂点上のグラフとし、となる整数と実数が選ばれていると仮定します。少なくとも 個の頂点のすべての部分集合に少なくとも 個の辺がある場合、頂点の部分集合のコレクション (「指紋」) と決定論的関数が存在するので、すべての独立集合 に対して、となるような が存在します。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle q}$${\displaystyle R,D}$${\displaystyle n\leq R+qD}$${\displaystyle U}$${\displaystyle R}$${\displaystyle D|U|/2}$${\displaystyle {\mathcal {F}}}$${\displaystyle q}$${\displaystyle f\colon {\mathcal {C}}\rightarrow {\mathcal {P}}(V(G))}$${\displaystyle I\subset V(G)}$${\displaystyle S\in {\mathcal {F}}}$${\displaystyle S\subset I\subset f(S)\cup S}$

非公式には、ハイパーグラフ コンテナの補題は、各独立集合に小さなフィンガープリント を割り当てることができることを示しています。これにより、同じフィンガープリントを持つすべての独立集合は、ハイパーグラフの頂点の数から離れたサイズを持つ、関連するコンテナである同じ大きな集合に属します。さらに、これらのフィンガープリントは小さく (したがって、コンテナの数も少ない)、ハイパーグラフのいくつかの単純な特性を使用して、本質的に最適な方法でそのサイズの上限を設定できます。 ${\displaystyle S\subset I}$${\displaystyle C=f(S)}$

一様ハイパーグラフに関連する次の表記を思い出します。 ${\displaystyle k}$${\displaystyle {\mathcal {H}}}$

• 正の整数 に対してを定義します。ここで です。${\displaystyle \Delta _{l}({\mathcal {H}}):=\max\{d_{H}(A)\mid A\subset V({\mathcal {H}}),|A|=l\}}$${\displaystyle 1\leq l\leq k}$${\displaystyle d_{\mathcal {H}}(A)=|\{e\in E({\mathcal {H}})\mid A\subset e\}|}$
• を の独立集合の集合とします。はそのような独立集合を表します。${\displaystyle {\mathcal {I}}({\mathcal {H}})}$${\displaystyle {\mathcal {H}}}$${\displaystyle I}$

この補題は、Balogh、Morris、Samotij、Saxtonの著作^{[9]に記載されているバージョンを述べる。}

を -一様ハイパーグラフとし、任意のといくつかのに対してが成り立つと仮定する。すると、集合と関数が存在し、 ${\displaystyle {\mathcal {H}}}$${\displaystyle k}$${\displaystyle l\in \{1,2,\ldots ,k\}}$${\displaystyle b,r\in \mathbb {N} }$${\displaystyle \Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H)|}{r}}}$${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$${\displaystyle f\colon {\mathcal {P}}(V(H))\rightarrow {\mathcal {C}}}$

• 任意の に対して、および が存在する。${\displaystyle I\in {\mathcal {I}}(H)}$${\displaystyle S\subset I}$${\displaystyle |S|\leq (k-1)b}$${\displaystyle I\subset f(S)}$
• ${\displaystyle |C|\leq |V(H)|-\delta r}$すべてのおよびに対して。${\displaystyle C\in {\mathcal {C}}}$${\displaystyle \delta =2^{-k(k+1)}}$

すべての-頂点-正則グラフがを満たすような絶対定数Cが存在することを示します。 ${\displaystyle n}$${\displaystyle d}$${\displaystyle G}$${\displaystyle i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2}}}}$

の自明な境界を使って、各サイズの独立集合の数を制限することができます。 が大きい場合、 をとります。これらのパラメータにより、d正則グラフは補題 1 の条件を満たし、したがって、 ${\displaystyle r}$${\displaystyle i(G,r)\leq {n \choose r}\leq {n \choose n/10}\leq 2^{0.48n}}$${\displaystyle r\leq n/10}$${\displaystyle r}$${\displaystyle \beta >10/n,q=\lfloor 1/\beta \rfloor ,R={\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}.}$${\displaystyle G}$

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}\leq {n \choose q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq \left({\frac {en}{q}}\right)^{q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq (e\beta n)^{\lfloor 1/\beta \rfloor }{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}.}$

すべてを 合計すると${\displaystyle 0\leq r\leq n}$

${\displaystyle i(G)\leq 2^{0.49n}+2^{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}+\lfloor 1/\beta \rfloor \log _{2}(e\beta n)}}$、

これを差し込むと、望ましい結果が得られます${\displaystyle \beta ={\sqrt {d\log d}}/n.}$

アーベル群の元の集合は、を満たす が存在しないとき、和が自由であると呼ばれます。の和が自由である部分集合は最大でも 個あることを示します。 ${\displaystyle A}$${\displaystyle x,y,z\in A}$${\displaystyle x+y=z}$${\displaystyle 2^{(1/2+o(1))n}}$${\displaystyle [n]:=\{1,2,\ldots ,n\}}$

これは、正則グラフ内の独立集合の数に関する上記の境界から導かれます。これを確認するには、補助グラフを構築する必要があります。まず、より低い次数の項まで、少なくとも より小さい要素を持つ和のない集合に焦点を絞ることができることに着目します(この補集合内の部分集合の数は最大 であるため)。 ${\displaystyle n^{2/3}}$${\displaystyle n/2}$${\displaystyle (n/2)^{n^{2/3}}2^{n/2+1}}$

ある部分集合 が与えられたとき、頂点集合と辺集合を持つ補助グラフ を定義し、 Sの各要素が より小さいので補助グラフが正則であることがわかります。次に、 が部分集合 の最小要素である場合、集合 はグラフ 内の独立集合です。次に、前の境界により、 の和のない部分集合の数は最大で であること がわかります。${\displaystyle S\subset \{1,2,\ldots ,\lceil n/2\rceil -1\}}$${\displaystyle G_{S}}$${\displaystyle [n]}$${\displaystyle \{\{x,y\}\mid x+s\equiv y{\pmod {n}}{\text{ for some }}s\in S\cup (-S)\}}$${\displaystyle 2|S|}$${\displaystyle n/2}$${\displaystyle S_{A}}$${\displaystyle n^{2/3}}$${\displaystyle A\subset [n]}$${\displaystyle A\backslash S_{A}}$${\displaystyle G_{S_{A}}}$${\displaystyle [n]}$

${\displaystyle (n/2)^{n^{2/3}}2^{n/2+}+{n/2 \choose n^{2/3}}2^{(1+O(n^{-1/3}{\sqrt {\log n}})){\frac {n}{2}}}\leq 2^{(1/2+O(n^{-1/3}\log n))n}.}$

我々は、頂点を持つ三角形のないグラフの数に漸近的に厳しい上限を与えることによって、ハイパーグラフコンテナ補題を使用して列挙質問に答える例を示します。^[10]${\displaystyle n}$

二部グラフには三角形がないので、頂点を持つ三角形が存在しないグラフの数は少なくとも 個であり、これはバランスの取れた完全二部グラフのすべての可能なサブグラフを列挙することによって得られます。 ${\displaystyle n}$${\displaystyle 2^{\lfloor n^{2}/4\rfloor }}$ ${\displaystyle K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }}$

頂点集合と辺集合 を持つ補助的な3 -一様ハイパーグラフHを構築できます。このハイパーグラフは、頂点上の三角形のないグラフの族がまさにこのハイパーグラフの独立集合 の集合であるという意味で三角形を「エンコード」します。 ${\displaystyle V(H)=E(K_{n})}$${\displaystyle E(H)=\{\{e_{1},e_{2},e_{3}\}\subset E(K_{n})=V(H)\mid e_{1},e_{2},e_{3}{\text{ form a triangle}}\}}$${\displaystyle n}$${\displaystyle {\mathcal {I}}(H)}$

上記のハイパーグラフは、次数分布が適切です。つまり、 の各辺、つまり の頂点は、ちょうど 個の三角形に含まれ、 の要素の各ペアは、最大で 1 個の三角形に含まれます。したがって、ハイパーグラフ コンテナの補題を (反復的に) 適用すると、ハイパーグラフのすべての三角形のないグラフ/独立集合を含む少数の三角形を含むコンテナの族が存在することが示されます。 ${\displaystyle K_{n}}$${\displaystyle V(H)}$${\displaystyle n-2}$${\displaystyle V(H)}$${\displaystyle n^{O(n^{3/2})}}$

まず、汎用ハイパーグラフ コンテナの補題を次のように 3 均一ハイパーグラフに特化します。

補題:任意の に対して、次が成り立つ が存在する。を平均次数の 3-一様ハイパーグラフとし、 と仮定する。すると、最大で 個のコンテナ の集合が存在し、${\displaystyle c>0}$${\displaystyle \delta >0}$${\displaystyle H}$${\displaystyle d\geq 1/\delta }$${\displaystyle \Delta _{1}(H)\leq cd,\Delta _{2}(H)\leq c{\sqrt {d}}}$${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$${\displaystyle |{\mathcal {C}}|\leq {|V(H)| \choose |V(H)|/{\sqrt {d}}}}$

• あらゆる に対して、 が存在する${\displaystyle I\in {\mathcal {I}}(H)}$${\displaystyle I\subset C\in {\mathcal {C}}}$
• ${\displaystyle |C|\leq (1-\delta )|V(H)|}$全ての${\displaystyle C\in {\mathcal {C}}}$

この補題を繰り返し適用すると、次の定理が得られます（以下で証明されます）。

定理:すべての に対して、次が成り立つ が存在する。任意の正の整数nに対して、次を満たす n頂点のグラフの集合が存在する。${\displaystyle \epsilon >0}$${\displaystyle C>0}$${\displaystyle {\mathcal {G}}}$${\displaystyle |{\mathcal {G}}|\leq n^{Cn^{3/2}}}$

• それぞれ三角形の数は${\displaystyle G\in {\mathcal {G}}}$${\displaystyle \epsilon n^{3}}$
• 頂点上の三角形のないグラフはそれぞれ何らかの に含まれます。${\displaystyle n}$${\displaystyle G\in {\mathcal {G}}}$

証明:上で定義したハイパーグラフを考えてみましょう。先ほど非公式に観察したように、ハイパーグラフは任意の に対して を満たします。したがって、 に対して上記の補題を適用して、の部分集合(つまり頂点上のグラフ) の集合を見つけ、${\displaystyle H}$${\displaystyle |V(H)|={n \choose 2},\Delta _{2}(H)=1,d(v)=n-2}$${\displaystyle v\in V(H)}$${\displaystyle H}$${\displaystyle c=1}$${\displaystyle {\mathcal {C}}}$${\displaystyle n^{O(n^{3/2})}}$${\displaystyle E(K_{n})}$${\displaystyle n}$

• あらゆる三角形のないグラフは何らかのグラフのサブグラフである。${\displaystyle C\in {\mathcal {C}}}$
• それぞれ最大で辺を持ちます。${\displaystyle C\in {\mathcal {C}}}$${\displaystyle (1-\delta ){n \choose 2}}$

これは、示したい結果ほど強力ではないので、コンテナの補題を繰り返し適用します。少なくとも 個の三角形を持つコンテナがあるとします。コンテナの補題を誘導サブハイパーグラフ に適用できます。 の平均次数は少なくとも です。これは、 内のすべての三角形が 内の辺であり、この誘導サブグラフには最大で 個の頂点があるためです。したがって、パラメータ を持つ補題 を適用し、 をコンテナのセットから削除して、 をカバーするコンテナであるこのコンテナのセットで置き換えることができます。 ${\displaystyle C\in {\mathcal {C}}}$${\displaystyle \epsilon n^{3}}$${\displaystyle H[C]}$${\displaystyle H[C]}$${\displaystyle 6\epsilon n}$${\displaystyle C}$${\displaystyle H[C]}$${\displaystyle {n \choose 2}}$${\displaystyle c=1/\epsilon }$${\displaystyle C}$${\displaystyle {\mathcal {I}}(H[C])}$

それぞれの三角形が 個未満のコンテナの最終的なコレクションが得られるまで、反復処理を続けることができます。このコレクションは大きすぎることはないことがわかります。誘導されたサブグラフはすべて、最大で個の頂点と少なくとも 個の平均次数を持ちます。つまり、各反復で最大で個の新しいコンテナが生成されます。さらに、コンテナのサイズは毎回 倍に縮小されるため、 に依存の制限回数の反復処理の後、反復処理は終了します。 ${\displaystyle {\mathcal {C}}}$${\displaystyle \epsilon n^{3}}$${\displaystyle {n \choose 2}}$${\displaystyle 6\epsilon n}$${\displaystyle n^{O(n^{3/2})}}$${\displaystyle 1-\delta }$${\displaystyle \epsilon }$

独立集合 (グラフ理論)
セメレディの定理
ゼメレディの規則性補題