Erdős–Faber–Lovász予想(Erdős–Faber–Lovász conjecture)とは、どの 2 辺も高々 1 頂点しか共有しない $n$ 頂点のハイパーグラフの辺は、交わる 2 辺が異なる色になるように $n$ 色で塗れる、という 1972 年の予想で、どの 2 つも高々 1 頂点しか共有しない $n$ 個の $n$ 頂点以下のクリークの和は $n$ 色で頂点を塗れる、と言い換えられる。頂点数が奇数の完全グラフや有限射影平面ではちょうど $n$ 色を要する。辺の大きさが 2 以下の場合は Vizing の定理から、どの 2 辺も交わる場合は Fisher の不等式から従い、貪欲法では $n\ge3$ のとき $2n-3$ 色で足りる。Kang、Kelly、Kühn、Methuku、Osthus が十分大きいすべての $n$ について証明した。
Erdős–Faber–Lovász予想(Erdős–Faber–Lovász conjecture)は、どの 2 つも高々 1 頂点しか共有しない $n$ 個のクリーク(それぞれ $n$ 頂点以下)の和として書けるグラフは、$n$ 色で頂点を塗り分けられる、という主張である。P. Erdős、V. Faber、L. Lovász が 1972 年に提起した。同じことを、どの 2 辺も高々 1 点で交わるハイパーグラフ(線形ハイパーグラフ)の言葉で言うと、$n$ 頂点の線形ハイパーグラフの辺は、交わる 2 辺がいつも異なる色になるように $n$ 色で塗れる、となる(KKKMO23 p. 1)。
$n$ が奇数のときの完全グラフ $K_n$、位数 $q$ の有限射影平面($n=q^2+q+1$)、1 本の直線とその外の 1 点からなる配置では $n$ 色がちょうど必要で、上界 $n$ は改善できない(同 p. 2)。予想は長く未解決だったが、D. Y. Kang、T. Kelly、D. Kühn、A. Methuku、D. Osthus が、十分大きいすべての $n$ について証明した(同 Theorem 1.1、p. 1)。この記事では、3 つの言い方が同値であることを証明し、どの 2 辺も交わる場合、辺の大きさが $2$ 以下の場合、$n\le3$ の場合に予想を証明し、貪欲法による上界 $\max\{2n-3,n\}$ を示す。
ハイパーグラフ、辺、次数、双対は ハイパーグラフ の定義「ハイパーグラフ」「接続行列と双対」に従う。とくにハイパーグラフ $\mathcal H=(V,E)$ の辺は $V$ の空でない部分集合で、同じ部分集合が 2 回辺になることはない。この記事のハイパーグラフは有限とし、$n:=\lvert V\rvert$ とする。
ハイパーグラフ $\mathcal H=(V,E)$ の相異なるどの 2 辺も高々 1 頂点しか共有しないとき、$\mathcal H$ は 線形(linear)であるという。写像 $c\colon E\to\{1,\dots,k\}$ で、共通の頂点をもつ相異なる 2 辺にいつも異なる値を与えるものを $k$-辺彩色 という。$k$-辺彩色をもつ最小の $k$ を $\mathcal H$ の 彩色指数(chromatic index)といい、$\chi'(\mathcal H)$ と書く。
2-一様なハイパーグラフは単純グラフで、線形であり、$\chi'$ は 辺彩色 の定義「辺彩色と辺彩色数」の辺彩色数である。
正の整数 $n$ について、次の 3 つの主張を考える。
(i) 大きさ $n$ の集合 $A_1,\dots,A_n$ のどの 2 つも高々 1 個の元しか共有しないならば、$\bigcup_iA_i$ の元を $n$ 色で塗って、どの $A_i$ にも $n$ 色すべてが現れるようにできる。
(ii) グラフ $G$ が、それぞれ $n$ 頂点以下の $n$ 個のクリーク $C_1,\dots,C_n$ の和で、どの 2 つのクリークも高々 1 頂点しか共有しないならば、$\chi(G)\le n$ である。
(iii) $n$ 頂点の線形ハイパーグラフ $\mathcal H$ は $\chi'(\mathcal H)\le n$ をみたす。
すべての $n$ についてこれらが成り立つ、という予想を Erdős–Faber–Lovász 予想 という。
ここで「グラフ $G$ がクリーク $C_1,\dots,C_n$ の和である」とは、$C_i\subseteq V(G)$ が $G$ で互いに隣接する頂点の集合で、$V(G)=\bigcup_iC_i$ であり、$G$ の辺はどれもある $C_i$ の 2 頂点を結ぶことをいう。3 つの主張は KKKMO23 p. 1 にそのまま並べられ、同値であると述べられている。次の節でこの同値性を証明する。
$\mathcal H=(V,E)$ を $n$ 頂点の線形ハイパーグラフ、$v\in V$ とする。
(a) $v$ を含む辺は $n$ 本以下である。
(b) $v$ を含む辺 $e$ と整数 $k\ge2$ について、$v$ を含み、大きさが $k$ 以上で、$e$ と異なる辺は $(n-\lvert e\rvert)/(k-1)$ 本以下である。
$v$ を含む相異なる 2 辺 $f,f'$ は $v$ を共有するので、線形性からほかの頂点を共有しない。つまり $f\setminus\{v\}$ と $f'\setminus\{v\}$ は交わらない。
(a) $f\setminus\{v\}$ が空になるのは $f=\{v\}$ の 1 本だけである。それ以外の辺については $f\setminus\{v\}$ が $V\setminus\{v\}$ の互いに交わらない空でない部分集合なので、高々 $n-1$ 本ある。合わせて $n$ 本以下である。
(b) $f\ni v$ が $e$ と異なれば、$f$ と $e$ は $v$ を共有するので、ほかの頂点を共有しない。よって $f\setminus\{v\}\subseteq V\setminus e$ である。$\lvert f\rvert\ge k$ なら $f\setminus\{v\}$ は $k-1$ 個以上の元をもつ。これらの集合は互いに交わらないので、本数を $N$ とすれば $N(k-1)\le\lvert V\setminus e\rvert=n-\lvert e\rvert$ である。$\square$
各 $n\ge1$ について、主張 (ii) と主張 (iii) は同値である。また (i) と (ii) も同値である。
(ii) ⇒ (iii). $\mathcal H=(V,E)$ を $n$ 頂点の線形ハイパーグラフとする。$E$ を頂点の集合とし、共通の頂点をもつ相異なる 2 辺を隣接させたグラフを $G$ とする($\mathcal H$ の線グラフ)。各 $v\in V$ について $C_v:=\{e\in E\mid v\in e\}$ は $G$ のクリークで、lem-efl-degree から $\lvert C_v\rvert\le n$ である。相異なる $v,w$ について $C_v\cap C_w$ は $v,w$ を両方含む辺の集合で、線形性から高々 1 本である。辺は空でないので $E=\bigcup_vC_v$ であり、$G$ の辺 $ee'$ は共通の頂点 $v$ について $C_v$ の 2 頂点を結ぶ。$C_v$ が空のときは、新しい頂点 1 個だけのクリークに取り替える(ほかのクリークと共有する頂点はなく、彩色数は変わらない)。よって (ii) から $\chi(G)\le n$ で、$G$ の頂点彩色は $\mathcal H$ の辺彩色にほかならないので $\chi'(\mathcal H)\le n$ である。
(iii) ⇒ (ii). $G$ を (ii) の仮定をみたすグラフとし、頂点 $x$ について $I(x):=\{i\mid x\in C_i\}$ とおく。$I(x)$ は空でない。$\lvert I(x)\rvert\ge2$ となる頂点 $x$ の全体を $W$ とする。$x\ne y$ がともに $W$ に属して $I(x)=I(y)$ なら、相異なる 2 つのクリークが $x,y$ を共有することになるので、$I$ は $W$ の上で単射である。また $x\ne y\in W$ について $\lvert I(x)\cap I(y)\rvert\ge2$ なら、やはり 2 つのクリークが $x,y$ を共有する。よって $\{1,\dots,n\}$ を頂点の集合とし、$I(x)$($x\in W$)を辺とするハイパーグラフ $\mathcal H$ は線形で、(iii) から $n$-辺彩色をもつ。$x,y\in W$ が $G$ で隣接すれば共通のクリークに属し、$I(x)\cap I(y)\ne\emptyset$ なので異なる色をもつ。こうして $W$ の頂点を $n$ 色で塗れる。
残りの頂点 $x\notin W$ はただ 1 つのクリーク $C_i$ に属し、$G$ での隣接頂点は $C_i\setminus\{x\}$ の高々 $n-1$ 個である。$x\notin W$ の頂点を 1 つずつ、隣接頂点に使われていない色で塗れば、$n$ 色で足りる。よって $\chi(G)\le n$ である。
(i) ⇒ (ii). (ii) の仮定をみたす $G$ について、各 $C_i$ に、ほかのどこにも現れない新しい元を加えて、大きさがちょうど $n$ の集合 $A_i$ にする。加えた元はほかの $A_j$ に属さないので、$A_i$ どうしが共有する元は $C_i$ どうしが共有する頂点と同じで、高々 1 個である。(i) の塗り方では、各 $A_i$ の $n$ 個の元に $n$ 色がすべて現れるので、$A_i$ の元の色は相異なる。$G$ の隣接する 2 頂点は同じ $C_i\subseteq A_i$ に属するので色が異なり、この塗り方を $V(G)$ に制限すれば $n$-彩色になる。
(ii) ⇒ (i). (i) の $A_1,\dots,A_n$ について、$\bigcup_iA_i$ を頂点の集合とし、同じ $A_i$ に属する 2 元を隣接させたグラフは、クリーク $A_1,\dots,A_n$ の和で (ii) の仮定をみたす。(ii) の $n$-彩色では、$n$ 頂点のクリーク $A_i$ の頂点の色は相異なるので、$n$ 色すべてが $A_i$ に現れる。$\square$
この証明の (ii) ⇒ (iii) で使ったグラフは、線グラフ をハイパーグラフに広げたものである。(iii) は (ii) を ハイパーグラフ の定義「接続行列と双対」の双対に移した形でもある。以下では (iii) の形で考える。
$n$ 頂点の線形ハイパーグラフ $\mathcal H$ の辺の大きさがすべて $2$ 以下ならば、$\chi'(\mathcal H)\le n$ である。
$n=1$ なら辺は高々 1 本で明らかなので、$n\ge2$ とする。大きさ $2$ の辺の全体は $V$ 上の単純グラフ $G$ をなし、最大次数 $\Delta(G)$ は $n-1$ 以下である。Vizingの定理 により $\chi'(G)\le\Delta(G)+1\le n$ なので、$G$ の辺を $n$ 色で塗る。残りの辺は 1 点集合 $\{v\}$ で、どの 2 つも交わらない。$\{v\}$ と交わる辺は $G$ で $v$ に接続する $\deg_G(v)\le n-1$ 本の辺だけなので、その色以外の色が $n$ 色の中に少なくとも 1 つ残り、それを $\{v\}$ に塗ればよい。$\square$
$n$ 頂点の線形ハイパーグラフ $\mathcal H=(V,E)$ のどの 2 辺も交わるならば、$\lvert E\rvert\le n$ であり、$\chi'(\mathcal H)=\lvert E\rvert\le n$ である。
線形性から、相異なる 2 辺はちょうど 1 頂点を共有する。$E$ の元は $V$ の相異なる部分集合なので、Fisherの不等式 の定理「非一様な Fisher の不等式」を $\lambda=1$ で使えば $\lvert E\rvert\le n$ である。どの 2 辺も交わるので、辺彩色ではすべての辺の色が相異なり、$\chi'(\mathcal H)=\lvert E\rvert$ である。$\square$
$n\ge2$ のとき、$n$ 頂点の線形ハイパーグラフ $\mathcal H$ は $\chi'(\mathcal H)\le\max\{2n-3,\,n\}$ をみたす。とくに $n\le3$ では Erdős–Faber–Lovász 予想が成り立つ。
辺を大きさの大きい順に並べ、この順に 1 本ずつ、すでに塗った辺のうち自分と交わるものに使われていない最小の色を塗る。辺 $e$ を塗る時点で $e$ と交わるすでに塗った辺が $m$ 本なら、$e$ の色は $m+1$ 以下である。
$\lvert e\rvert=k\ge2$ のとき、すでに塗った辺はどれも大きさが $k$ 以上である。$e$ と交わるそのような辺は、$e$ のどれか 1 つの頂点 $v$ を含む。線形性から 2 つ以上の頂点を含むことはないので、$v\in e$ ごとに lem-efl-degree (b) を使って
$$
m\le k\cdot\frac{n-k}{k-1}
$$
を得る。ここで
$$
2(n-2)(k-1)-k(n-k)=n(k-2)+(k-2)^2\ge0
$$
なので $m\le2(n-2)$ で、$e$ の色は $2n-3$ 以下である。
$\lvert e\rvert=1$、つまり $e=\{v\}$ のとき、$e$ と交わる辺は $v$ を含むほかの辺で、lem-efl-degree (a) から $n-1$ 本以下である。よって $e$ の色は $n$ 以下である。
合わせて $\chi'(\mathcal H)\le\max\{2n-3,n\}$ である。$n=2,3$ では $2n-3\le n$ なので $\chi'(\mathcal H)\le n$ で、$n=1$ では辺が $\{v\}$ の高々 1 本なので明らかである。$\square$
上界の $2n-3$ は $n$ のおよそ $2$ 倍である。予想が述べる上界 $n$ との差を詰めた結果は、後の節「知られていること」で挙げる。
次の 3 つの例では $\chi'(\mathcal H)=n$ となり、予想の上界 $n$ は一般には下げられない(KKKMO23 p. 2 が挙げる 3 つの構成)。
$n\ge3$ を奇数とし、$\mathcal H$ を完全グラフ $K_n$(2-一様な線形ハイパーグラフ)とする。辺彩色 の定理「完全グラフの辺彩色数」により $\chi'(K_n)=n$ である。直接には次のように分かる。辺の本数は $n(n-1)/2$ で、1 つの色の辺は互いに交わらないので高々 $(n-1)/2$ 本である。よって色は $n$ 個以上要る。
$q\ge2$ とし、位数 $q$ の有限射影平面の点の全体を $V$、各直線をその上の点の集合とみたものを辺とする。射影平面 の定理「有限射影平面の位数」により $\lvert V\rvert=q^2+q+1=:n$ で、直線も $n$ 本ある。射影平面の公理から、相異なる 2 点を通る直線はただ 1 本なので $\mathcal H$ は線形で、相異なる 2 直線はちょうど 1 点で交わる。どの 2 辺も交わるので、prop-efl-intersecting により $\chi'(\mathcal H)=n$ である。$q=2$ は Fano平面 で、$n=7$ である。
$n\ge3$ とし、$V=\{1,\dots,n\}$ の上に、辺 $\{2,\dots,n\}$ と $\{1,i\}$($2\le i\le n$)の $n$ 本をとる。$n\ge4$ では 射影平面 の例「反例:1 本の直線とその外の 1 点」の $k=n-2$ の配置であり($n=3$ では三角形 $K_3$)、$\{1,i\}$ どうしは $1$ だけを、$\{1,i\}$ と $\{2,\dots,n\}$ は $i$ だけを共有する。よって線形で、どの 2 辺も交わるので $\chi'(\mathcal H)=n$ である。
ex-efl-complete の辺の大きさは $2$ だが、残りの 2 つの例では辺の大きさが $n$ とともに大きくなる。prop-efl-intersecting が示すように、どの 2 辺も交わる線形ハイパーグラフで辺が $n$ 本あれば上界に達する。後の 2 つの例はこの形である。
KKKMO23 p. 1 によれば、予想は 1972 年に提起され、次の結果が積み重ねられてきた。
十分大きいすべての $n$ について、$n$ 頂点の線形ハイパーグラフの彩色指数は $n$ 以下である。
仮定を 1 つ外すと結論が成り立たなくなる例を並べる。
| 外した仮定 | 例 | 成り立たない結論 |
|---|---|---|
| (iii) の線形性 | $n\ge3$ のとき、$\{1,\dots,n\}$ の部分集合で $1$ を含むものすべてを辺とする | どの 2 辺も $1$ を共有するので $\chi'=2^{n-1}>n$ となり、$\chi'\le n$ が成り立たない |
| (ii) の「各クリークは $n$ 頂点以下」 | $n\ge2$ のとき、$C_1$ を $n+1$ 頂点のクリークとし、$C_2,\dots,C_n$ を新しい 1 頂点ずつにとる | $G$ は $K_{n+1}$ を含むので $\chi(G)=n+1$ となり、$\chi(G)\le n$ が成り立たない |
| (ii) の「2 つのクリークの共有は 1 頂点以下」 | $n=3$、$C_1=\{a,b,c\}$、$C_2=\{a,b,d\}$、$C_3=\{c,d\}$($C_1,C_2$ は 2 頂点を共有) | $G$ は 4 頂点の完全グラフなので $\chi(G)=4$ となり、$\chi(G)\le3$ が成り立たない |
1 行目では、どの 2 辺も交わる族として $2^{n-1}$ 本の辺がとれる。線形性があれば prop-efl-intersecting によりこの本数は $n$ 以下に抑えられ、線形性が効く場所がよく分かる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する