Erdős–Hajnal予想

同義語:Erdős–Hajnal conjectureErdős–Hajnalの予想

概要

Erdős–Hajnal 予想(Erdős–Hajnal conjecture)とは、どのグラフ $H$ にも $\varepsilon(H)>0$ があって、$H$ を誘導部分グラフに含まない $n$ 頂点のグラフは大きさ $n^{\varepsilon(H)}$ 以上のクリークか独立集合をもつ、という未解決の予想である。一般のグラフでは Ramsey の定理による $\log n$ 程度の大きさしか保証されないので、1 つの誘導部分グラフを禁止するだけで多項式の大きさに上がるかを問う。予想が成り立つ $H$ の族は置換の操作で閉じ、問題は素なグラフに帰着する。$5$ 頂点以下のすべての $H$ では証明されているが、一般の $H$ では未解決である。

$$\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}} $$

前提知識: Ramseyの定理, 誘導部分グラフ, 補グラフ

Erdős–Hajnal 予想(Erdős–Hajnal conjecture)とは、どのグラフ $H$ についても定数 $\varepsilon(H)>0$ があって、$H$ を誘導部分グラフとして含まない $n$ 頂点のグラフは、大きさ $n^{\varepsilon(H)}$ 以上のクリークか独立集合をもつ、という予想である。未解決である。
背景には Ramseyの定理 がある。どの $n$ 頂点のグラフも、大きさがおよそ $\frac12\log_2n$ 以上のクリークか独立集合をもち、逆に Erdős の確率的な議論により、どちらも $2\log_2n$ 程度の大きさしかもたないグラフがある。予想は、ただ 1 つのグラフ $H$ を誘導部分グラフとして禁止するだけで、この対数の大きさが多項式の大きさに跳ね上がると主張する。Erdős と Hajnal は、$\exp(c\sqrt{\log n})$ の大きさまでは成り立つことを示した。

問い答え
主張$H$ を含まないグラフは $n^{\varepsilon(H)}$ 以上のクリークか独立集合をもつ
状況未解決。$5$ 頂点以下のすべての $H$ で成り立つことが示されている
一般の $H$ で知られる大きさ$\exp(c\sqrt{\log n})$(Erdős–Hajnal)、さらに $2^{c\sqrt{\log n\log\log n}}$
組み立て方性質は補グラフ・誘導部分グラフ・置換で保たれる(thm-eh-substitution)
未解決の最小の場合$6$ 頂点以上の素なグラフ(総説 Chu16 の時点ではどれも未解決)

定義

この記事のグラフは、頂点が有限個の単純グラフとする。グラフ $G$ の頂点の集合で、どの 2 頂点も隣接するものを クリーク、どの 2 頂点も隣接しないものを 独立集合 といい、それぞれの大きさの最大値を $\omega(G)$、$\alpha(G)$ と書く。$\hom(G)=\max(\alpha(G),\omega(G))$ とおく。グラフ $H$ と同型な誘導部分グラフをもたないグラフを $H$ を含まないグラフという。

Erdős–Hajnal 性

グラフ $H$ が Erdős–Hajnal 性 をもつとは、定数 $c>0$ と $\varepsilon>0$ があって、$H$ を含まないどのグラフ $G$(頂点数 $n\ge1$)も
$$ \hom(G)\ge c\,n^{\varepsilon} $$
をみたすことをいう。

定数 $c$ は $1$ にとり直せる。実際、$N=c^{-2/\varepsilon}$ とおくと $n\ge N$ で $c\,n^\varepsilon\ge n^{\varepsilon/2}$ であり、$2\le n< N$ では $\hom(G)\ge2$(どの 2 頂点もクリークか独立集合をなす)なので、$\varepsilon'=\min(\varepsilon/2,\ \log2/\log N)$ について $\hom(G)\ge n^{\varepsilon'}$ が成り立つ($N\le2$ なら $\varepsilon'=\varepsilon/2$ でよい)。

Erdős–Hajnal 予想

すべての有限グラフ $H$ は Erdős–Hajnal 性をもつ。

予想は Erdős と Hajnal の論文 EH89 にある(Chu16 Conjecture 1.1, p. 1)。

基本の性質と簡単な場合

補グラフと誘導部分グラフ
  1. $H$ が Erdős–Hajnal 性をもつことと、補グラフ $\overline H$ がもつことは同値である。
  2. $H$ が Erdős–Hajnal 性をもてば、$H$ の誘導部分グラフ $H'$ もそれをもつ。
  3. $2$ 頂点以下のグラフは Erdős–Hajnal 性をもつ。

1:$G$ が $H$ を含まないことと $\overline G$ が $\overline H$ を含まないことは同値で、$\alpha(\overline G)=\omega(G)$、$\omega(\overline G)=\alpha(G)$ なので $\hom(\overline G)=\hom(G)$ である。2:$H'$ を含まないグラフは $H$ も含まない($H$ の誘導部分グラフ $H'$ が $H$ の中にある)ので、$H$ の定数がそのまま使える。3:$1$ 頂点のグラフを含まないグラフは空のグラフしかない。$H=K_2$ なら $H$ を含まないグラフは辺がなく $\alpha(G)=n$、$H=\overline{K_2}$ なら完全グラフで $\omega(G)=n$ である。$\square$

完全グラフ

$t\ge2$ とする。$K_t$ を含まない $n$ 頂点のグラフは $\alpha(G)\ge\frac12n^{1/(t-1)}$ をみたす。とくに $K_t$ と $\overline{K_t}$ は Erdős–Hajnal 性をもつ。

$k=\alpha(G)$ とする。辺を赤、辺でない対を青に塗ると、赤い $K_t$ も青い $K_{k+1}$ もないので、Ramseyの定理 の定理「Ramsey の定理(2 色の場合)」から
$$ n< R(t,k+1)\le\binom{t+k-1}{t-1}=\prod_{i=1}^{t-1}\frac{k+i}{i}\le(k+1)^{t-1} $$
である($(k+i)/i\le k+1$)。よって $n^{1/(t-1)}< k+1\le2k$ である($k\ge1$)。$\overline{K_t}$ は prop-eh-basic の 1 による。$\square$

道 $P_4$

$P_4$ を含まない $n$ 頂点のグラフ $G$ は $\alpha(G)\,\omega(G)\ge n$ をみたし、したがって $\hom(G)\ge\sqrt n$ である。とくに $P_4$ は Erdős–Hajnal 性をもつ。

$n$ についての帰納法による。$n=1$ なら明らかである。$n\ge2$ なら、誘導部分グラフ の記事の定理「$P_4$-free なグラフの分解」により $G$ か $\overline G$ が連結でない。$G$ が連結でなければ、$V$ を空でない $V_1,V_2$ に分けて間に辺がないようにでき、$G_j=G[V_j]$、$n_j=\lvert V_j\rvert$ とおくと $\alpha(G)=\alpha(G_1)+\alpha(G_2)$、$\omega(G)=\max(\omega(G_1),\omega(G_2))$ である。$G_j$ も $P_4$ を含まないので、帰納法の仮定から
$$ \alpha(G)\,\omega(G)\ge\alpha(G_1)\omega(G_1)+\alpha(G_2)\omega(G_2)\ge n_1+n_2=n $$
である。$\overline G$ が連結でなければ、$\overline G$ も $P_4$ を含まない($\overline{P_4}\cong P_4$)ので同じ議論を $\overline G$ に当て、$\alpha,\omega$ が入れ替わることを使う。最後に $\max(\alpha,\omega)^2\ge\alpha\omega\ge n$ である。$\square$

主定理:置換で保たれること

大きなグラフの Erdős–Hajnal 性を小さなグラフから導く操作として、頂点をグラフで置き換える置換がある。

置換と素なグラフ

頂点の集合が交わらないグラフ $H_1,H_2$ と $v\in V(H_1)$ について、頂点の集合を $(V(H_1)\setminus\{v\})\cup V(H_2)$ とし、$V(H_1)\setminus\{v\}$ の中と $V(H_2)$ の中ではそれぞれ $H_1,H_2$ の辺を、$u\in V(H_1)\setminus\{v\}$ と $w\in V(H_2)$ の間には $u$ が $H_1$ で $v$ に隣接するときに限り辺を置いたグラフ $H$ を、$v$ に $H_2$ を置換して得られるグラフ という。
グラフ $H$ の頂点の集合 $M$ が、$M$ の外のどの頂点も $M$ のすべてに隣接するかどれにも隣接しないような集合であるとき、$M$ を 加群 という。$2\le\lvert M\rvert<\lvert V(H)\rvert$ の加群をもたないグラフを 素 という。

加群 $M$($2\le\lvert M\rvert<\lvert V(H)\rvert$)があれば、$m\in M$ について、$H$ は $H[(V(H)\setminus M)\cup\{m\}]$ の頂点 $m$ に $H[M]$ を置換したグラフで、どちらも $H$ より頂点が少ない。たとえば $P_3$ の両端は加群をなすので、$3$ 頂点の素なグラフはない。$4$ 頂点の素なグラフは $P_4$ だけで、$5$ 頂点の素なグラフは $C_5$、$P_5$、$\overline{P_5}$、bull(三角形 $a_1a_2a_3$ に辺 $a_1b_1,a_2b_2$ を加えたもの)の 4 つである(Chu16 pp. 3–4)。

Alon–Pach–Solymosi の定理

$H_1,H_2$ が Erdős–Hajnal 性をもてば、$H_1$ の頂点に $H_2$ を置換して得られるグラフ $H$ も Erdős–Hajnal 性をもつ。

$h=\lvert V(H_1)\rvert$ とし、置換する頂点を $v$ とする。$h=1$ なら $H=H_2$ なので $h\ge2$ とする。$H_j$ の定数を $c_j,\varepsilon_j$ とする。$G$ を $H$ を含まない $n$ 頂点のグラフとし、$m=\lceil n^{1/(2h)}\rceil$ とおく。$1\le m\le n$、$m\le2n^{1/(2h)}$ である。
場合 1:$m$ 頂点の集合 $S$ で、$G[S]$ が $H_1$ を含まないものがある。 このとき $\hom(G)\ge\hom(G[S])\ge c_1m^{\varepsilon_1}\ge c_1n^{\varepsilon_1/(2h)}$ である。
場合 2:どの $m$ 頂点の集合も $H_1$ と同型な誘導部分グラフを含む。 $m\ge h$ である。$G[T]\cong H_1$ となる $h$ 頂点の集合 $T$ の個数を $N$ とする。$m$ 頂点の集合 $S$ と $T\subset S$ の組を数えると、各 $S$ が少なくとも 1 つの $T$ を含み、各 $T$ を含む $S$ は $\binom{n-h}{m-h}$ 個なので、
$$ N\ge\binom nm\Big/\binom{n-h}{m-h}=\prod_{i=0}^{h-1}\frac{n-i}{m-i}\ge\Bigl(\frac nm\Bigr)^h $$
である($m\le n$ から $(n-i)/(m-i)\ge n/m$)。各 $T$ について同型 $\psi_T\colon V(H_1)\to T$ を 1 つ選ぶ。制限 $\psi_T|_{V(H_1)\setminus\{v\}}$ は $V(H_1)\setminus\{v\}$ から $V(G)$ への単射で、そのような単射は $n^{h-1}$ 個以下なので、ある単射 $\psi'$ を制限にもつ $T$ が $N/n^{h-1}\ge n/m^h\ge2^{-h}n^{1/2}$ 個以上ある。それらの $T$ について $w=\psi_T(v)$ を集めた集合を $W$ とする。$T$ が異なれば $\psi_T(v)$ も異なるので $\lvert W\rvert\ge2^{-h}n^{1/2}$ である。
$W$ の頂点 $w$ は $\psi'$ の像に入らず、$u\in V(H_1)\setminus\{v\}$ について、$w$ が $\psi'(u)$ に隣接することは $u$ が $H_1$ で $v$ に隣接することと同値である($\psi_T$ が同型だから)。したがって、$G[W]$ が $H_2$ と同型な誘導部分グラフ $G[W']$ をもてば、$\psi'(V(H_1)\setminus\{v\})\cup W'$ が誘導するグラフは、$v$ に $H_2$ を置換したグラフ $H$ と同型になり、仮定に反する。よって $G[W]$ は $H_2$ を含まず、$\hom(G)\ge c_2\lvert W\rvert^{\varepsilon_2}\ge c_22^{-h\varepsilon_2}n^{\varepsilon_2/2}$ である。
どちらの場合も、$c=\min(c_1,c_22^{-h\varepsilon_2})$、$\varepsilon=\min(\varepsilon_1/(2h),\varepsilon_2/2)$ について $\hom(G)\ge c\,n^\varepsilon$ である。$\square$

この定理は Alon、Pach、Solymosi による(APS01。Chu16 Theorem 2.2, p. 3 は証明の考え方を、$H_1\setminus v$ のある複製が多くの仕方で $H_1$ に延び、延ばす頂点の中に $H_2$ が現れる、と紹介している)。上の証明はその考え方に沿って定数まで書いたものである。

素な部分への帰着

$H$ の誘導部分グラフで素なものがすべて Erdős–Hajnal 性をもてば、$H$ も Erdős–Hajnal 性をもつ。とくに、$4$ 頂点以下のすべてのグラフと、$P_4$ を含まないすべてのグラフは Erdős–Hajnal 性をもつ。

頂点数についての帰納法による。$H$ が素なら仮定による。$2$ 頂点以下なら prop-eh-basic の 3 による。そうでなければ加群 $M$ があり、$H$ は $H_1=H[(V(H)\setminus M)\cup\{m\}]$ の $m$ に $H_2=H[M]$ を置換したグラフである。$H_1,H_2$ は $H$ より小さい誘導部分グラフで、その素な誘導部分グラフは $H$ の素な誘導部分グラフなので、帰納法の仮定から Erdős–Hajnal 性をもち、thm-eh-substitution から $H$ ももつ。
$4$ 頂点以下のグラフの素な誘導部分グラフは、$2$ 頂点以下のグラフと $P_4$ だけである($3$ 頂点の素なグラフはなく、$4$ 頂点の素なグラフは $P_4$ だけ)。$P_4$ を含まないグラフの素な誘導部分グラフは $2$ 頂点以下である。実際、$P_4$ を含まない $3$ 頂点以上のグラフ $F$ では、誘導部分グラフ の記事の定理「$P_4$-free なグラフの分解」により $F$ か $\overline F$ が連結でなく、その連結成分で $2$ 頂点以上のもの、またはすべて $1$ 頂点なら任意の 2 頂点が加群になる。これらは prop-eh-basic の 3 と prop-eh-p4 により Erdős–Hajnal 性をもつ。$\square$

$P_4$ を含まないグラフについては、prop-eh-p4 が直接 $\varepsilon=1/2$ を与える。cor-eh-prime の証明で得られる定数は、置換を重ねるたびに小さくなる。

知られている結果

主な結果を年の順に挙げる(2026 年 11 月の時点)。

  • 一般の $H$ での下界。 Erdős と Hajnal は、どの $H$ にも $c(H)>0$ があって、$H$ を含まないグラフが $\hom(G)\ge e^{c(H)\sqrt{\log n}}$ をみたすことを示した(EH89。Chu16 Theorem 1.1, p. 1)。Bucić、Nguyen、Scott、Seymour はこれを $2^{c\sqrt{\log n\log\log n}}$($n\ge2$)に改良した(BNSS23)。多項式の大きさ $n^{\varepsilon}$ は一般には得られていない。
  • 総説の時点。 Chu16 によると、Erdős–Hajnal 性が示されていた素なグラフは、$4$ 頂点以下のものと bull(Chudnovsky–Safra CS08。bull を含まないグラフは $\hom(G)\ge n^{1/4}$ をみたす)だけであり(Chu16 Theorem 2.3, p. 4)、$P_5$、$\overline{P_5}$、$C_5$ は未解決で、$6$ 頂点以上の素なグラフで Erdős–Hajnal 性が示されたものはなかった(同 p. 5)。
  • $C_5$。 Chudnovsky、Scott、Seymour、Spirkl が $C_5$ の Erdős–Hajnal 性を示した(CSSS23)。
  • $P_5$。 Nguyen、Scott、Seymour が $P_5$ の Erdős–Hajnal 性を示した(NSS23)。$\overline{P_5}$ は prop-eh-basic の 1 による。これで $5$ 頂点の素なグラフ $C_5$、$P_5$、$\overline{P_5}$、bull がすべて Erdős–Hajnal 性をもつので、cor-eh-prime により $5$ 頂点以下のすべてのグラフがそれをもつ。

同値な言い換え。 予想は、トーナメント(どの 2 頂点の間にもちょうど一方の向きの辺がある有向グラフ)について、1 つの部分トーナメントを禁止すると推移的な部分トーナメントの大きさが多項式になる、という予想と同値である(Alon–Pach–Solymosi APS01。Chu16 Conjecture 4.1, p. 6)。また、$H$ を含まないグラフには、大きさ $n^{\varepsilon(H)}$ の交わらない 2 つの頂点の集合 $A,B$ で、$A$ と $B$ の間がすべて辺か、すべて辺でないものがあること(Erdős–Hajnal–Pach)は、すべての $H$ で成り立つ(Chu16 Theorem 3.1, p. 5)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
1 つのグラフ $H$ を禁止すること(conj-eh-main)Erdős の下界の $n$ 頂点のグラフ$\hom(G)\ge c\,n^\varepsilon$。$\hom(G)< 2\log_2n+2$ のグラフがある
$P_4$ を含まないこと(prop-eh-p4)$C_5$$\alpha\,\omega\ge n$。$\alpha(C_5)=\omega(C_5)=2$ で $\alpha\omega=4< 5$
$K_t$ を含まないこと(prop-eh-complete)完全グラフ $K_n$$\alpha\ge\frac12n^{1/(t-1)}$。$\alpha(K_n)=1$
反例の確かめ

要点:各行で左の条件だけが外れていることを確かめる。

確かめを開く

1 行目:Ramseyの定理 の定理「Erdős の下界」により $k\ge3$ で $R(k,k)>2^{k/2}$ なので、$n=\lfloor2^{k/2}\rfloor$ 頂点のグラフで $\hom(G)\le k-1$ のものがある。$2^{k/2}< n+1$ から $k< 2\log_2(n+1)\le2\log_2n+2$ である。$n$ を大きくすると、$c\,n^\varepsilon$ はどの $c,\varepsilon>0$ についても $2\log_2n+2$ を超える。

2 行目:$C_5$ は $0,1,2,3$ が誘導された $P_4$ をなす。三角形がなく、独立集合は $\{0,2\}$ のように 2 頂点までである。

3 行目:$K_n$($n\ge t$)は $K_t$ を含み、$\alpha(K_n)=1<\frac12n^{1/(t-1)}$($n> 2^{t-1}$ のとき)である。$K_n$ は $\omega=n$ なので $\hom$ は大きく、conj-eh-main の結論は成り立つ。

歴史と広がり

  • 予想の出典。 Chu16 は、予想が Erdős と Hajnal の 1989 年の論文 EH89 にあり、同じ論文に $e^{c\sqrt{\log n}}$ の結果があると紹介している(p. 1)。BNSS23 は、予想を 1977 年のものとしている。
  • パーフェクトな誘導部分グラフへの言い換え。 パーフェクトなグラフ $P$ では $\alpha(P)\omega(P)\ge\lvert V(P)\rvert$ なので、予想は「$H$ を含まないグラフは $n^{\varepsilon}$ 頂点以上のパーフェクトな誘導部分グラフをもつ」と同値である(Chu16 Theorem 1.3・Conjecture 1.2, p. 2。パーフェクトについては パーフェクトグラフ定理)。prop-eh-p4 はこの考え方の最も簡単な例である。
  • 置換の役割。 thm-eh-substitution は、小さなグラフから大きなグラフの Erdős–Hajnal 性を作る、知られている唯一の操作である(Chu16 p. 3、総説の時点)。そのため、残るのは素なグラフの場合である。

関連項目

参考文献

[3]
N. Alon; J. Pach; J. Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica, 2001, pp. 155–170

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