コンテナ法

同義語:ハイパーグラフのコンテナ法container methodhypergraph container methodmethod of hypergraph containers

概要

コンテナ法(hypergraph container method)とは、ハイパーグラフの独立集合の全体を、少数の「コンテナ」と呼ばれる集合のどれかに収めることで、独立集合を数え上げる方法である。グラフの場合は、次数の大きい頂点から順に調べる Kleitman–Winston の手順により、各独立集合が少数の点からなる指紋と、指紋だけで決まる小さい集合の間に挟まれる。これを使うと、$n$ 頂点の $C_4$ を含まないグラフの個数は $2^{\Theta(n^{3/2})}$ になる。3 一様ハイパーグラフのコンテナ補題からは、三角形を含まないグラフの個数の 2 を底とする対数が $(\frac14+o(1))n^2$ であることが導かれる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ハイパーグラフ, 独立集合, 極値グラフ理論

コンテナ法(hypergraph container method)は、ハイパーグラフの独立集合の全体を、少数の「コンテナ」と呼ばれる集合に収める方法である。各独立集合はどれかのコンテナに含まれ、各コンテナは辺をほとんど含まない(あるいは小さい)。コンテナの個数と大きさが分かれば、独立集合の個数は「コンテナの個数 × 1 つのコンテナの部分集合の個数」で上から抑えられる。
組合せ論の多くの対象は、あるハイパーグラフの独立集合として表せる。たとえば頂点集合 $\{1,\dots,n\}$ の上の三角形を含まないグラフは、完全グラフ $K_n$ の辺を頂点とし、三角形をなす 3 本の辺を 1 つの辺とする 3 一様ハイパーグラフの独立集合である。三角形を含まないグラフの個数を数えるには、この独立集合を数えればよい。
この方法の原型は、D. J. Kleitman と K. J. Winston が 1980 年代の初めに C₄(長さ 4 の閉路)を含まないグラフの個数を数えるのに使った議論である。名前は A. A. Sapozhenko による。一般の一様ハイパーグラフについてのコンテナ補題は、J. Balogh、R. Morris、W. Samotij と、D. Saxton、A. Thomason が 2015 年に独立に発表した(BMS18 pp. 1–3)。
この記事では、グラフ(2 一様ハイパーグラフ)の場合のコンテナ補題を Kleitman–Winston の手順で完全に証明し、それを使って $n$ 頂点の C₄ を含まないグラフの個数が $2^{O(n^{3/2})}$ であることを示す。3 一様ハイパーグラフのコンテナ補題は主張と帰属にとどめ、それを認めたうえで、三角形を含まないグラフの個数が $2^{(1/4+o(1))n^2}$ であることを導く。

定義

ハイパーグラフ $\mathcal H=(V,E)$ は、有限集合 $V$ と $V$ の部分集合の族 $E$ の組である(ハイパーグラフ の定義「ハイパーグラフ」)。すべての辺の大きさが $k$ のとき $k$ 一様 といい、2 一様ハイパーグラフはグラフである。

独立集合とコンテナ

$\mathcal H=(V,E)$ をハイパーグラフとする。

  1. $I\subseteq V$ が $E$ のどの元も部分集合として含まないとき、$I$ を $\mathcal H$ の 独立集合 という。独立集合の全体を $\mathcal I(\mathcal H)$、その個数を $i(\mathcal H)$、ちょうど $m$ 個の元をもつ独立集合の個数を $i(\mathcal H,m)$ と書く。
  2. $V$ の部分集合の族 $\mathcal C$ で、各 $I\in\mathcal I(\mathcal H)$ に対して $I\subseteq C$ となる $C\in\mathcal C$ があるものを、$\mathcal I(\mathcal H)$ の コンテナの族 といい、その元を コンテナ という。

グラフ $G$ の場合、1 は 独立集合 の定義「独立集合と独立数」の独立集合と同じである。$\{V\}$ はいつもコンテナの族なので、意味があるのは、コンテナの個数が少なく、各コンテナが小さいか辺を少ししか含まない族である。独立集合はどれかのコンテナの部分集合なので、
$$ i(\mathcal H)\le\sum_{C\in\mathcal C}2^{|C|}\le|\mathcal C|\cdot2^{\max_{C\in\mathcal C}|C|},\qquad i(\mathcal H,m)\le\sum_{C\in\mathcal C}\binom{|C|}m $$
である。これがコンテナ法での数え上げの基本の形である。

グラフのコンテナ補題

Kleitman–Winston の手順

$G$ を $n$ 頂点のグラフとし、頂点に全順序を 1 つ固定する。$U\subseteq V(G)$ について、$G[U]$ を $U$ が誘導する部分グラフ、$e_G(U)$ をその辺の本数、$\deg_G(v,U):=|N_G(v)\cap U|$ と書く。

最大次数順

$A\subseteq V(G)$ の 最大次数順 とは、$A$ の元の並べ方 $(v_1,\dots,v_{|A|})$ で、各 $j$ について $v_j$ が $G[A\setminus\{v_1,\dots,v_{j-1}\}]$ で次数が最大の頂点であるもの(同点は固定した全順序で先の頂点を選ぶ)である。

独立集合 $I$ と整数 $q\le|I|$ が与えられたとき、$A:=V(G)$、$S:=\emptyset$ から始めて、$s=1,\dots,q$ について次を行う(Sam15 §2、pp. 2–3)。

  1. $A$ の最大次数順 $(v_1,\dots,v_{|A|})$ をとり、$v_j\in I$ となる最小の $j$ を $j_s$ とする。
  2. $v_{j_s}$ を $A$ から $S$ へ移し、$v_1,\dots,v_{j_s-1}$ を $A$ から除く。
  3. $N_G(v_{j_s})\cap A$ を $A$ から除く。
    最後の $S$ と $A$ を $S(I)$、$A(I)$ と書く。$|I\setminus S|\ge q-(s-1)\ge1$ と次の補題の 1 により、$s$ 回目の 1 で $I\cap A$ は空でないので、$j_s$ は定まる。
手順の性質

$I\in\mathcal I(G)$、$|I|\ge q$ とする。

  1. 各回の終わりで $S\subseteq I$、$I\setminus S\subseteq A$ である。
  2. 各回の操作は $j_s$ だけで決まる。とくに $A(I)$ は $S(I)$ だけで決まり、同じ手順を $S(I)$ に施すと同じ $S(I)$ と $A(I)$ が得られる。
  3. $s$ 回目の 1 で $A':=A\setminus\{v_1,\dots,v_{j_s-1}\}$ とおくと、その回に $A$ から除かれる頂点($S$ へ移すものを含む)は $j_s+\deg_G(v_{j_s},A')$ 個以上で、$\deg_G(v_{j_s},A')\ge2e_G(A')/|A'|$ である。

1。 2 で除く $v_1,\dots,v_{j_s-1}$ は $j_s$ の最小性により $I$ に属さず、3 で除く頂点は $I$ の元 $v_{j_s}$ の隣接頂点なので、$I$ が独立集合であることから $I$ に属さない。$I$ の元で $A$ から出ていくのは $S$ へ移す $v_{j_s}$ だけである。
2。 最大次数順は $A$ だけで決まり、$A$ の変え方は $j_s$ だけで決まるので、帰納法により各回の $A$ と $S$ は $(j_1,\dots,j_s)$ だけで決まる。$S(I)$ の元は加えた順に $v_{j_1},v_{j_2},\dots$ である。$s$ 回目の開始時の $A$ が決まっていれば、最大次数順で $S(I)$ の $s$ 番目の元の位置として $j_s$ が読み取れる。よって $(j_1,\dots,j_q)$ は $S(I)$ から順に復元できる。同じ手順を $S(I)$ に施すと、1 により $S(I)\setminus\{v_{j_1},\dots,v_{j_{s-1}}\}\subseteq A$ で、$v_1,\dots,v_{j_s-1}$ は $I$ にも $S(I)$ にも属さないので、同じ $j_s$ が選ばれる。
3。 2 で $j_s-1$ 個、$S$ へ移す 1 個、3 で $N_G(v_{j_s})\cap A'$ の元($v_1,\dots,v_{j_s-1}$ はすでに除いた)を除く。$v_{j_s}$ は $G[A']$ の最大次数の頂点なので、その次数は平均次数 $2e_G(A')/|A'|$ 以上である。$\square$

補題の主張と証明

グラフのコンテナ補題

$G$ を $n$ 頂点のグラフとし、整数 $q\ge1$ と実数 $R>0$、$\beta\in[0,1]$ が
$$ R\ge e^{-\beta q}n $$
を満たすとする。$|U|\ge R$ となるすべての $U\subseteq V(G)$ で $e_G(U)\ge\beta\binom{|U|}2$ が成り立つとする。このとき、次が成り立つ。

  1. $q$ 元集合の族 $\mathcal S$ と写像 $f\colon\mathcal S\to2^{V(G)}$ で、$|\mathcal S|\le\binom nq$、すべての $S\in\mathcal S$ で $|f(S)|\le R$、かつ $|I|\ge q$ の各独立集合 $I$ について $S\subseteq I\subseteq S\cup f(S)$ となる $S\in\mathcal S$ があるものが存在する。
  2. $m\ge q$ なら $i(G,m)\le\binom nq\binom{\lfloor R\rfloor}{m-q}$ である。

1 の $S$ を $I$ の 指紋(fingerprint)といい、$S\cup f(S)$ がコンテナである。コンテナは指紋だけで決まるので、その個数は高々 $\binom nq$ で、大きさは $q+R$ 以下である。

手順の各回で A が 1−β 倍以下に縮むことを使う

$\mathcal S:=\{S(I):I\in\mathcal I(G),\ |I|\ge q\}$、$f(S(I)):=A(I)$ と定める。lem-cont-algorithm の 2 により $A(I)$ は $S(I)$ だけで決まるので $f$ は定まり、1 により $S(I)\subseteq I\subseteq S(I)\cup A(I)$ である。
指紋の個数。 lem-cont-algorithm の 2 により $S(I)$ は列 $(j_1,\dots,j_q)$ で決まる。$j_s\ge1$ で、各回に $A$ から $j_s$ 個以上の頂点が除かれるので $j_1+\cdots+j_q\le n$ である。このような正の整数の列は、部分和 $j_1< j_1+j_2< \cdots< j_1+\cdots+j_q$ が $\{1,\dots,n\}$ の $q$ 元部分集合を定めることと 1 対 1 に対応するので、$\binom nq$ 個ある。よって $|\mathcal S|\le\binom nq$ である。
$|f(S)|\le R$。 ある $I$ で $|A(I)|>R$ だったとして矛盾を導く。$s$ 回目の 1 の $A$ と $A'$ は終わりの $A(I)$ を含むので $|A'|>R$ で、仮定から $e_G(A')\ge\beta\binom{|A'|}2$、すなわち $2e_G(A')/|A'|\ge\beta(|A'|-1)$ である。lem-cont-algorithm の 3 により、この回に除かれる頂点は
$$ j_s+\beta(|A'|-1)=j_s+\beta(|A|-j_s)\ge\beta|A| $$
個以上である($|A'|=|A|-j_s+1$、$\beta\le1$ を使った)。よって各回で $|A|$ は $1-\beta$ 倍以下になり、$1-\beta\le e^{-\beta}$ から
$$ |A(I)|\le(1-\beta)^qn\le e^{-\beta q}n\le R $$
となって矛盾する。
2。 $|I|=m\ge q$ の独立集合 $I$ は、指紋 $S\in\mathcal S$ と $(m-q)$ 元集合 $I\setminus S\subseteq f(S)$ で決まる。$|f(S)|\le\lfloor R\rfloor$ なので、その選び方は $\binom{\lfloor R\rfloor}{m-q}$ 通り以下である。$\square$

仮定は「大きい頂点集合はどれも辺をある密度以上含む」というものである。この仮定のもとで、手順は独立集合の外の頂点を各回にまとめて捨て、少数の指紋のあとに残る候補 $A$ を $R$ 個以下に絞る。独立集合の個数を数える問題が、指紋の数え上げ($\binom nq$)と、小さい集合の部分集合の数え上げに分かれる。thm-cont-graph の 2 は Sam15 の Lemma 1(p. 4)である。1 は同 Lemma 2(pp. 4–5)の結論と同じ形で、同書は Lemma 2 を平均次数についての別の仮定で述べ、Lemma 1 の仮定からも同じ結論が出ることを p. 5 で注意している。同書はどちらの補題も Kleitman と Winston の仕事に含まれていたものとしている。

長さ 4 の閉路を含まないグラフの個数

頂点集合 $\{1,\dots,n\}$ の上のグラフで、長さ 4 の閉路 $C_4$ を部分グラフとして含まないものの個数を $f_n$ とする。同型なグラフも頂点の番号が違えば別に数える。グラフ $F$ が $C_4$ を含まないことは、相異なる 2 頂点の共通の隣接頂点が高々 1 個であることと同値である。

C₄ を含まないグラフの個数

$n\to\infty$ のとき
$$ \Bigl(\frac12-o(1)\Bigr)n^{3/2}\le\log_2f_n\le\Bigl(\frac2{\ln2}+o(1)\Bigr)n^{3/2}. $$
とくに $f_n=2^{\Theta(n^{3/2})}$ である。

頂点を 1 つずつ付け加え、隣接頂点の集合をコンテナ補題で数える

下界。 Kővári–Sós–Turánの定理 の定理「$K_{2,t}$ の極値数の大きさ」により、$C_4=K_{2,2}$ を含まない $n$ 頂点のグラフで辺が $\operatorname{ex}(n,K_{2,2})\ge(\frac12-o(1))n^{3/2}$ 本のものがある。その全域部分グラフはどれも $C_4$ を含まないので、$f_n\ge2^{\operatorname{ex}(n,K_{2,2})}$ である。
以下は上界の証明である。各段階で付け加える頂点の隣接頂点の集合が、ある補助グラフの独立集合になることに thm-cont-graph を使う。
符号化。 $C_4$ を含まないグラフ $G$ に対し、$G_n:=G$ とし、$i=n,n-1,\dots,2$ の順に、$G_i$ の次数最小の頂点(同点は番号の小さいほう)を $v_i$、$G_{i-1}:=G_i-v_i$ とする。残る 1 頂点を $v_1$ とする。$N_i:=N_{G_i}(v_i)\subseteq\{v_1,\dots,v_{i-1}\}$、$d_i:=|N_i|$ とおく。$G$ は列 $(v_1,\dots,v_n)$ と $N_2,\dots,N_n$ から復元できる。$d_i$ は $G_i$ の最小次数で、1 頂点を除くと各頂点の次数は高々 1 減るので、$G_{i-1}$ の最小次数は $d_i-1$ 以上である。また $G_i$ は $C_4$ を含まない。
$m\ge1$、$0\le d\le m$ について、$m$ 頂点の $C_4$ を含まないグラフ $F$ で最小次数が $d-1$ 以上のものと、$d$ 元集合 $N\subseteq V(F)$ で $F$ に $N$ の各点と結ぶ新頂点 $x$ を加えたグラフ $F+x$ が $C_4$ を含まないものを考え、$N$ の個数の $F$ についての最大値を $g_m(d)$、$g_m:=\max_dg_m(d)$ とする。$G_{i-1}$ を決めたあとの $(d_i,N_i)$ の選び方は $i\,g_{i-1}$ 通り以下なので、
$$ f_n\le n!\prod_{m=1}^{n-1}(m+1)\,g_m . $$
補助グラフ。 $F+x$ が $C_4$ を含まなければ、$N$ の相異なる 2 点 $a,b$ は $F$ で共通の隣接頂点 $z$ をもたない(もてば $x,a,z,b$ が $C_4$ をなす)。$a,b$ が $F$ で共通の隣接頂点をもつときに結ぶグラフを $H$ とすると、$N$ は $H$ の独立集合で、$g_m(d)\le i(H,d)$ である。
$H$ の辺の密度。 $d\ge2$ とする。$F$ では 2 点の共通の隣接頂点は高々 1 個なので、$B\subseteq V(F)$ について $e_H(B)=\sum_{z}\binom{|N_F(z)\cap B|}2$ である。$\sum_z|N_F(z)\cap B|=\sum_{b\in B}\deg_F(b)\ge(d-1)|B|$ なので、$x\mapsto x(x-1)/2$ の凸性と、この関数が $x\ge\frac12$ で増加すること(下の $y$ が $1$ より小さければ右辺は $0$ 以下)から、$y:=(d-1)|B|/m$ として $e_H(B)\ge m\,y(y-1)/2$ である。$|B|\ge R:=2m/(d-1)$ なら $y\ge2$、$y-1\ge y/2$ なので
$$ e_H(B)\ge\frac{(d-1)^2|B|^2}{4m}\ge\beta\binom{|B|}2,\qquad\beta:=\frac{(d-1)^2}{2m}. $$
$\beta\le1$ も成り立つ。実際、共通の隣接頂点を数えると $m\binom{d-1}2\le\sum_z\binom{\deg_F(z)}2\le\binom m2$ なので $(d-1)(d-2)\le m-1$ で、$(d-1)^2\le(m-1)+(d-1)\le2m$ である。
場合 1:$d\ln m\le\sqrt m$。 $g_m(d)\le\binom md\le m^d\le e^{\sqrt m}$。
場合 2:$d\ln m>\sqrt m$。 このとき $m\ge2$、$d\ge2$ で、$d-1\ge d/2$ から $(d-1)^2>m/(4\ln^2m)$ である。$q:=\lceil2m\ln m/(d-1)^2\rceil$ とおくと $1\le q<1+8\ln^3m$、$\beta q\ge\ln m$ なので $e^{-\beta q}m\le1< R$ で、thm-cont-graph の仮定が成り立つ。$d\le q$ なら $i(H,d)\le m^d\le m^q$。$d>q$ なら $k:=d-q$ とおくと $1\le k\le d-1$ で、thm-cont-graph の 2 と $\binom Lk\le(eL/k)^k$ から
$$ i(H,d)\le m^q\Bigl(\frac{eR}k\Bigr)^k\le m^q\Bigl(\frac{2em}{k^2}\Bigr)^k=m^q\Bigl(\Bigl(\frac{\sqrt{2em}}k\Bigr)^k\Bigr)^2\le m^q\,e^{2\sqrt{2m/e}}\le m^q\,e^{2\sqrt m} $$
である。ここで $x>0$ について $(\gamma/x)^x\le e^{\gamma/e}$($x\ln(\gamma/x)$ は $x=\gamma/e$ で最大)を使った。
どちらの場合も $g_m\le\exp(\ln m+8\ln^4m+2\sqrt m)$ である。$n!\le n^n$、$\prod(m+1)\le n^n$、$\sum_{m< n}2\sqrt m\le2n^{3/2}$ から
$$ \ln f_n\le2n^{3/2}+3n\ln n+8n\ln^4n, $$
両辺を $\ln2$ で割れば上界が得られる。$\square$

符号化で最小次数の頂点を除いていくのは、補助グラフ $H$ の密度を、付け加える頂点の次数 $d$ だけで下から抑えるためである。$d$ が小さいときは $N$ の選び方を直接数え、$d$ が大きいときは $H$ が密になるのでコンテナ補題が効く。この型の評価 $f_n\le2^{O(n^{3/2})}$ は Kleitman と Winston によるもので(Sam15 §3.4 の Theorem 8、pp. 9–11)、上の証明の定数は最良を目指していない。

3 一様ハイパーグラフのコンテナ補題

3 一様ハイパーグラフ $\mathcal H$ について、$v(\mathcal H)$ を頂点の個数、$d$ を平均次数(頂点を含む辺の個数の平均)とする。$\Delta_1(\mathcal H)$ を 1 頂点を含む辺の個数の最大値、$\Delta_2(\mathcal H)$ を相異なる 2 頂点をともに含む辺の個数の最大値とする。

3 一様ハイパーグラフのコンテナ補題

任意の $c>0$ に対して $\delta>0$ が存在し、次が成り立つ。3 一様ハイパーグラフ $\mathcal H$ が $d\ge\delta^{-1}$、$\Delta_1(\mathcal H)\le c\,d$、$\Delta_2(\mathcal H)\le c\sqrt d$ を満たすなら、$V(\mathcal H)$ の部分集合の族 $\mathcal C$ で
$$ |\mathcal C|\le\binom{v(\mathcal H)}{v(\mathcal H)/\sqrt d} $$
かつ次の 2 条件を満たすものがある。

  1. $\mathcal H$ の各独立集合は、ある $C\in\mathcal C$ に含まれる。
  2. すべての $C\in\mathcal C$ で $|C|\le(1-\delta)v(\mathcal H)$ である。
出典と使い方

これは BMS18 の p. 4 に述べられている形で、一般の $k$ 一様ハイパーグラフについての形は J. Balogh、R. Morris、W. Samotij(BMS15)と D. Saxton、A. Thomason(ST15)による。この記事では証明しない。thm-cont-graph と同じく、少数の指紋から定まるコンテナに独立集合を収めるという形だが、各コンテナは全体より一定の割合だけ小さいことしか言わない。そこで、コンテナが誘導する部分ハイパーグラフに補題を繰り返し当てて、辺の少ないコンテナまで細かくする。三角形のハイパーグラフにこの反復を施すと、次の定理が得られる(BMS18 Theorem 2.1、p. 5。同書はこれを thm-cont-3uniform から導いている。この記事ではこれも証明しない)。

三角形を含まないグラフのコンテナ

各 $\varepsilon>0$ に対して定数 $c_\varepsilon>0$ が存在し、各 $n$ について、頂点集合 $\{1,\dots,n\}$ の上のグラフの族 $\mathcal G$ で次を満たすものがある。

  1. $|\mathcal G|\le n^{c_\varepsilon n^{3/2}}$。
  2. 各 $G\in\mathcal G$ の三角形の個数は $\varepsilon n^3$ より少ない。
  3. $\{1,\dots,n\}$ の上の三角形を含まないグラフは、どれもある $G\in\mathcal G$ の部分グラフである。
三角形のハイパーグラフと補題の仮定
次数の計算を開く

$K_n$ の辺を頂点とし、三角形をなす 3 本の辺を辺とする 3 一様ハイパーグラフ $\mathcal H_n$ では、$K_n$ の各辺はちょうど $n-2$ 個の三角形に含まれ、相異なる 2 本の辺を含む三角形は高々 1 個である。よって $d=\Delta_1(\mathcal H_n)=n-2$、$\Delta_2(\mathcal H_n)\le1$ で、thm-cont-3uniform の次数の仮定の形に合う。コンテナが誘導する部分ハイパーグラフでは次数がそろわなくなるので、繰り返し当てるには平均次数と最大次数の比を管理する必要がある。その処理は BMS18 の §2 にある。

三角形を含まないグラフの個数

頂点集合 $\{1,\dots,n\}$ の上の三角形を含まないグラフの個数を $T_n$ とする。thm-cont-triangle-containers を使うと、その 2 を底とする対数の主要項が決まる。次の定理の証明は、この記事では証明しない thm-cont-triangle-containers に依存する。

三角形を含まないグラフの個数

$n\to\infty$ のとき
$$ \log_2T_n=\Bigl(\frac14+o(1)\Bigr)n^2 . $$

コンテナの辺の本数を Mantel の定理の三角形の個数の下界で抑える

下界。 完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ は $\lfloor n^2/4\rfloor$ 本の辺をもち、その全域部分グラフはどれも二部グラフなので三角形を含まない。よって $T_n\ge2^{\lfloor n^2/4\rfloor}$ である。
上界。 $\varepsilon>0$ を固定し、thm-cont-triangle-containers を $\varepsilon/3$ に当てて族 $\mathcal G$ をとる。各 $G\in\mathcal G$ の辺の本数 $e(G)$ は $(\frac14+\varepsilon)n^2$ より少ない。実際、$e(G)\ge(\frac14+\varepsilon)n^2$ なら、Mantelの定理 の定理「辺の本数による三角形の個数の下界」により、$G$ の三角形は
$$ \frac{4e(G)}{3n}\Bigl(e(G)-\frac{n^2}4\Bigr)\ge\frac43\Bigl(\frac14+\varepsilon\Bigr)n\cdot\varepsilon n^2\ge\frac\varepsilon3n^3 $$
個以上あり、$\mathcal G$ の条件 2 に反する。三角形を含まないグラフはどれもある $G\in\mathcal G$ の部分グラフなので、
$$ T_n\le\sum_{G\in\mathcal G}2^{e(G)}\le n^{c_{\varepsilon/3}n^{3/2}}\,2^{(1/4+\varepsilon)n^2} $$
である。$\log_2T_n\le c_{\varepsilon/3}n^{3/2}\log_2n+(\frac14+\varepsilon)n^2$ で、$\varepsilon>0$ は任意なので、$\log_2T_n\le(\frac14+o(1))n^2$ を得る。$\square$

より精密な結果として、三角形を含まないグラフのほとんどすべてが二部グラフであることが、P. Erdős、D. J. Kleitman、B. L. Rothschild により知られている(BMS18 p. 7)。コンテナ法の利点は、同じ議論がほかの禁止部分グラフや、無作為な部分集合の中での問題にも、ほぼそのまま使えることにある。

例と反例

thm-cont-graph の手順を小さいグラフで実行すると、指紋とコンテナの様子が見える。

Petersen グラフでの手順

Petersenグラフ $P$ は 3-正則で、独立集合 の例「Petersen グラフの独立数」により独立数は 4 である。$q=1$ のとき、最初の最大次数順の先頭の頂点 $v_1$ は次数 3 である。独立集合 $I$ が $v_1$ を含めば $j_1=1$ で、$A$ からは $v_1$ とその 3 個の隣接頂点が除かれ、6 頂点が残る。$v_1\notin I$ なら $v_1$ は 2 で除かれる。どちらの場合も各回に 1 頂点以上が除かれる。頂点を 0 から 9 と番号づけ、外周 $0$–$1$–$2$–$3$–$4$、内側 $5$–$7$–$9$–$6$–$8$、輻 $i$–$(i+5)$ とした場合に、大きさ $q$ 以上の独立集合すべてで手順を実行すると次のようになる。

$q$大きさ $q$ 以上の独立集合現れる指紋の個数$\binom{10}q$$\lvert f(S)\rvert$ の最大値
17510106
26530453
335301201

指紋の個数が $\binom{10}q$ より小さいのは、thm-cont-graph の証明の数え方が、$j_1+\cdots+j_q\le n$ を満たす列のうち実際には現れないものまで数えているからである。$q=3$ では $|f(S)|\le1$ なので、大きさ 3 以上の独立集合は指紋の 3 点と、高々 1 点の追加で決まる。

thm-cont-c4 と thm-cont-triangle-free は、$n$ が大きいときに三角形を含まないグラフが $C_4$ を含まないグラフよりはるかに多いことを示す。小さい $n$ では様子が違い、すべてのグラフを調べると次のようになる。

$n$123456
三角形を含まないグラフ $T_n$127413885789
$C_4$ を含まないグラフ $f_n$128545487984
$2^{\lfloor n^2/4\rfloor}$1241664512

$n\le6$ では $f_n>T_n$ である。$\log_2T_n$ は $n^2/4$ の程度、$\log_2f_n$ は $n^{3/2}$ の程度で増えるので、$n$ が大きくなるといずれ $T_n>f_n$ となる。
次の表の各行は、thm-cont-graph の仮定を 1 つだけ外したときに結論 2 が成り立たなくなる例である。

外した仮定例成り立たなくなる結論
$\lvert U\rvert\ge R$ の集合の辺の密度辺のない 10 頂点のグラフ、$q=2$、$\beta=1$、$R=2$$i(G,10)=1$ だが $\binom{10}2\binom28=0$
$R\ge e^{-\beta q}n$2 つの $K_7$ の交わらない和($n=14$)、$q=1$、$\beta=1/4$、$R=3$$i(G,2)=49$ だが $\binom{14}1\binom31=42$
反例の確かめ
各行の確かめを開く

1 行目では $e^{-2}\cdot10\approx1.35\le2$ なので $R\ge e^{-\beta q}n$ は成り立つ。辺の密度の仮定は、大きさ 2 の集合 $U$ で $e_G(U)=0< \binom22$ となって成り立たない。頂点全体が独立集合なので $i(G,10)=1$ である。

2 行目では、大きさ $r\ge3$ の $U$ が 2 つの $K_7$ に $a$ 個と $r-a$ 個ずつ入るとき、$e_G(U)=\binom a2+\binom{r-a}2\ge2\binom{r/2}2=\frac{r(r-2)}4$ で、$r\ge3$ なら $\frac{r(r-2)}4\ge\frac14\binom r2$ なので密度の仮定は成り立つ($\binom x2$ の凸性を使った)。一方 $e^{-1/4}\cdot14\approx10.9>3$ である。独立集合は各 $K_7$ から高々 1 点ずつとるものなので、大きさ 2 のものは $7\cdot7=49$ 個ある。

注意

一般のコンテナ補題について

thm-cont-graph は、大きい頂点集合の辺の密度だけを仮定する。$k\ge3$ の $k$ 一様ハイパーグラフでは、辺が頂点の組に偏っていないことを $\Delta_1,\Delta_2$ のような次数の最大値で測る必要があり、thm-cont-3uniform の仮定はその形をしている。この記事の 2 つの数え上げでは、個数の対数が禁止する部分グラフの極値数と同じ程度になっている。$C_4$ では thm-cont-c4 のとおり $\log_2f_n$ と $\operatorname{ex}(n,C_4)$ がどちらも $n^{3/2}$ の程度で、三角形では thm-cont-triangle-free のとおり $\log_2T_n$ の主要項が Mantelの定理 の極値数 $\lfloor n^2/4\rfloor$ の主要項と一致する。

文献
文献の所在を開く

Kleitman–Winston の手順とグラフのコンテナ補題は Sam15 の §2(pp. 2–5)に、$C_4$ を含まないグラフの個数への応用は同 §3.4(pp. 9–11)にある。コンテナ法の歴史、3 一様ハイパーグラフのコンテナ補題、三角形を含まないグラフへの応用は BMS18 の §1–§2(pp. 1–7)にまとめられている。一般の一様ハイパーグラフのコンテナ補題の原論文は BMS15 と ST15、$C_4$ を含まないグラフの数え上げの原論文は KW82 である。

関連項目

参考文献

[1]
Wojciech Samotij, Counting independent sets in graphs, European Journal of Combinatorics 48 (2015), pp. 5–18, 2015, arXiv 版 v1(arXiv:1412.0940)の頁。§2 の手順と Lemma 1・Lemma 2(pp. 2–5)、§3.4 の Theorem 8(C₄ を含まないグラフの個数、pp. 9–11)
[2]
József Balogh, Robert Morris, Wojciech Samotij, The method of hypergraph containers, Proceedings of the International Congress of Mathematicians (Rio de Janeiro 2018), Vol. IV, pp. 3059–3092, 2018, arXiv 版 v1(arXiv:1801.04584)の頁。§1 の歴史(pp. 1–4)、3 一様ハイパーグラフのコンテナ補題(p. 4)、Theorem 2.1(p. 5)、Erdős–Kleitman–Rothschild の結果への言及(p. 7)
[3]
József Balogh, Robert Morris, Wojciech Samotij, Independent sets in hypergraphs, Journal of the American Mathematical Society 28 (2015), no. 3, pp. 669–709, 2015
[4]
David Saxton, Andrew Thomason, Hypergraph containers, Inventiones Mathematicae 201 (2015), no. 3, pp. 925–992, 2015
[5]
Daniel J. Kleitman, Kenneth J. Winston, On the number of graphs without 4-cycles, Discrete Mathematics 41 (1982), no. 2, pp. 167–172, 1982

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する