コンテナ方式

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

これらの問題は、次のような形式の質問として表現できます。有限頂点集合 $V$ 上の辺集合 $E$ を持つハイパーグラフ $H （つまり、サイズ制約のある$ $V$ の部分集合の集合）が与えられたとき、 $H$ の独立集合（つまり、 $E$ の要素を含まない $V$ の部分集合）について何が言えるでしょうか？ハイパーグラフコンテナ補題は、このような質問に取り組むための方法を提供します。

歴史

極値グラフ理論の基礎問題の一つは、1907年のマンテルと1940年代のトゥランの研究に遡り、ある固定された禁制グラフ $Hのコピーを部分グラフとして含まないグラフを特徴付けることである。別の領域では、加法組合せ論における動機づけとなる問いの一つは、$ $k項$ 等差数列を含まない整数集合がどれだけの大きさになり得るかを理解することであり、このサイズの上限はロス( ) とセメレディ(一般の $k$ ) によって与えられている。 $k=3$

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

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

主なアイデアと非公式な声明

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

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

$H$ における最大独立集合の大きさはどれくらいですか？ $H$ における最大サイズの独立集合の集合はどのように見えるでしょうか？
$H$ には独立集合がいくつありますか？ $H$ における「典型的な」独立集合はどのようなものですか？

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

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

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

ハイパーグラフコンテナ補題は、ハイパーグラフ内の独立集合族の構造とサイズを理解するための強力なアプローチを提供します。ハイパーグラフコンテナ法の核心は、ハイパーグラフから、以下の性質を満たす頂点の部分集合であるコンテナの集合を抽出することです。

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

コンテナという名称は、この最後の条件を暗示しています。このようなコンテナは、独立集合（コンテナの部分集合）の族を特徴づけたり、ハイパーグラフの独立集合を列挙したり（コンテナの可能なすべての部分集合を単純に考慮するだけで）するための効果的なアプローチとなることがよくあります。

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

グラフコンテナアルゴリズム

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

表記

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

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

クライトマン・ウィンストンアルゴリズム

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

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

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

分析

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

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

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}

、

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

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つの項をバランス/最小化するを選ぶ必要があります。この結果は、頂点を最大次数で並べること（を最小化すること）の価値を示しています。 $q$ $|A(j_{1},\ldots j_{q})|$

補題

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

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

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

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

ハイパーグラフコンテナ補題

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

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

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

声明

この補題はバログ、モリス、サモティジ、サクストンの著作に載っているバージョンを述べる。^[9]

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

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

アプリケーション例

通常のグラフ

独立集合の数の上限

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

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

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}.

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

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

、

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

和自由集合

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

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

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

(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] $n$

非公式声明

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

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

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

三角形のないグラフの数の上限

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

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

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

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

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

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

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

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

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

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

参照

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

参考文献

^ ダニエル・クライトマン、ケネス・ウィンストン (1980). 「格子の漸近数」.離散数学年報. 6 : 243–249 . doi :10.1016/S0167-5060(08)70708-8. ISBN 9780444860484。
^ ダニエル・クライトマン、ケネス・ウィンストン (1982). 「4-サイクルを持たないグラフの数について」.離散数学. 31 (2): 167– 172. doi : 10.1016/0012-365X(82)90204-7 .
^ サポジェンコ、アレクサンダー (2003)。「キャメロン・エルドス予想」。ドクラディ・アカデミ・ナウク。393 : 749 – 752.
^ サポジェンコ、アレクサンダー (2002). 「アーベル群における和自由集合の数の漸近解析」.国立アカデミー紀要. 383 : 454–458 .
^ Sapozhenko, Alexander (2005)、「コンテナシステムと列挙問題」、確率アルゴリズム：基礎と応用、コンピュータサイエンス講義ノート、第3777巻、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp. 1– 13、doi :10.1007/11571155_1、ISBN 978-3-540-29498-6、 2022年2月13日取得
^ Saxton, David; Thomason, Andrew (2015). 「ハイパーグラフコンテナ」. Inventiones Mathematicae . 201 (3): 925– 992. arXiv : 1204.6595 . Bibcode :2015InMat.201..925S. doi :10.1007/s00222-014-0562-8. S2CID 119253715.
^ Balogh, József; Morris, Robert; Samotij, Wojciech (2015). 「ハイパーグラフにおける独立集合」. Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650.
^ サモティ、ヴォイチェフ (2015). 「グラフ内の独立集合を数える」。欧州組合せ論ジャーナル。48 : 5–18.arXiv : 1412.0940 。土井：10.1016/j.ejc.2015.02.005。S2CID 15850625。
^ Balogh, József; Morris, Robert; Samotij, Wojciech (2015). 「ハイパーグラフにおける独立集合」. Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650.
^ Balogh, József; Morris, Robert; Samotij, Wojciech (2018). 「ハイパーグラフコンテナ法」.国際数学者会議論文集: リオデジャネイロ. arXiv : 1801.04584 .

[1] ダニエル・クライトマン、ケネス・ウィンストン (1980). 「格子の漸近数」.離散数学年報. 6 : 243–249 . doi :10.1016/S0167-5060(08)70708-8. ISBN 9780444860484。

[2] ダニエル・クライトマン、ケネス・ウィンストン (1982). 「4-サイクルを持たないグラフの数について」.離散数学. 31 (2): 167– 172. doi : 10.1016/0012-365X(82)90204-7 .

[3] サポジェンコ、アレクサンダー (2003)。「キャメロン・エルドス予想」。ドクラディ・アカデミ・ナウク。393 : 749 – 752.

[4] サポジェンコ、アレクサンダー (2002). 「アーベル群における和自由集合の数の漸近解析」.国立アカデミー紀要. 383 : 454–458 .

[5] Sapozhenko, Alexander (2005)、「コンテナシステムと列挙問題」、確率アルゴリズム：基礎と応用、コンピュータサイエンス講義ノート、第3777巻、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp. 1– 13、doi :10.1007/11571155_1、ISBN 978-3-540-29498-6、 2022年2月13日取得

[6] Saxton, David; Thomason, Andrew (2015). 「ハイパーグラフコンテナ」. Inventiones Mathematicae . 201 (3): 925– 992. arXiv : 1204.6595 . Bibcode :2015InMat.201..925S. doi :10.1007/s00222-014-0562-8. S2CID 119253715.

[7] Balogh, József; Morris, Robert; Samotij, Wojciech (2015). 「ハイパーグラフにおける独立集合」. Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650.

[8] サモティ、ヴォイチェフ (2015). 「グラフ内の独立集合を数える」。欧州組合せ論ジャーナル。48 : 5–18.arXiv : 1412.0940 。土井：10.1016/j.ejc.2015.02.005。S2CID 15850625。

[9] Balogh, József; Morris, Robert; Samotij, Wojciech (2015). 「ハイパーグラフにおける独立集合」. Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650.

[10] Balogh, József; Morris, Robert; Samotij, Wojciech (2018). 「ハイパーグラフコンテナ法」.国際数学者会議論文集: リオデジャネイロ. arXiv : 1801.04584 .