Kneser予想
概要
Kneser予想（Kneser's conjecture）とは、$k\ge1$、$n\ge2k-1$ のとき、$n$ 元集合の $k$ 元部分集合を頂点とし交わらない 2 つを辺で結んだ Kneser グラフ $\mathrm{KG}(n,k)$ の彩色数が $n-2k+2$ であるという主張であり、Lovász が 1978 年に Borsuk–Ulam の定理を使って証明した。$n-2k+2$ 色の塗り方は最小元で色を決めれば作れる。$n-2k+1$ 色で塗れないことは、点を球面 $S^{n-2k+1}$ に一般の位置に置き、開半球に入る集合の色で球面を覆う Greene の議論で示せる。$\mathrm{KG}(3k-1,k)$ は三角形を含まないのに彩色数が $k+1$ であり、クリークや独立集合による下界が届かない例になる。
前提知識: 彩色数, Borsuk–Ulamの定理, n次元球面
Kneser 予想（Kneser's conjecture）は、$n$ 元集合の $k$ 元部分集合を頂点とし、交わらない 2 つを辺で結んだグラフ（Kneserグラフ）$\mathrm{KG}(n,k)$ の彩色数が $n-2k+2$ である、という主張である。M. Kneser が 1955 年に問題として出し、L. Lovász が 1978 年に Borsuk–Ulamの定理 を使って証明した（MZ04 pp. 2–3）。このうち下界を言い換えると、$k$ 元部分集合の全体を $n-2k+1$ 個の組に分けると、どれかの組に交わらない 2 つの $k$ 元部分集合が入る。
$n-2k+2$ 色で塗れることは易しい。難しいのは $n-2k+1$ 色では塗れないことで、$\mathrm{KG}(3k-1,k)$ は三角形を含まないのに彩色数が $k+1$ になるので、クリークや独立集合の大きさからの評価では届かない。この記事では、塗り方を構成して上界を示し、下界を J. E. Greene（2002）による短い証明で示す。点を球面に一般の位置に置き、半球に入る集合の色で球面を覆って、Borsuk–Ulam の定理の被覆の形に持ち込む。例として Petersenグラフ $\mathrm{KG}(5,2)$ を扱う。
定義
$n\ge1$ について $[n]:=\{1,\dots,n\}$ とし、$k\ge1$ について $[n]$ の $k$ 元部分集合の全体を $\binom{[n]}{k}$ と書く。グラフと彩色数の用語は 彩色数 の記事のものとする（$\chi(G)$ は彩色数、$\omega(G)$ はクリーク数、$\alpha(G)$ は独立数）。
$n\ge k\ge1$ とする。$\binom{[n]}{k}$ を頂点の集合とし、$S\cap T=\emptyset$ となる 2 頂点 $S,T$ を辺で結んだ単純グラフを Kneser グラフ（Kneser graph）といい、$\mathrm{KG}(n,k)$ と書く。
$\mathrm{KG}(n,k)$ を $K(n,k)$ と書く文献もある。頂点は $\binom nk$ 個で、各頂点の次数は $\binom{n-k}{k}$ である（$S$ と交わらない $k$ 元集合は $[n]\setminus S$ の $k$ 元部分集合）。
- $k=1$ のとき、1 元集合どうしは異なれば交わらないので、$\mathrm{KG}(n,1)$ は 完全グラフ $K_n$ である。
- $k\le n<2k$ のとき、2 つの $k$ 元部分集合は大きさの和が $2k>n$ なので必ず交わり、$\mathrm{KG}(n,k)$ は辺をもたない。
- $n=2k$ のとき、$S$ と交わらない $k$ 元集合は補集合 $[2k]\setminus S$ だけなので、$\mathrm{KG}(2k,k)$ は $\frac12\binom{2k}{k}$ 本の辺が互いに端点を共有しないグラフ（完全マッチング）である。
- $\mathrm{KG}(5,2)$ は 10 頂点・3-正則のグラフで、Petersenグラフ である。
$k\ge1$、$n\ge2k-1$ とする。このとき
$$
\chi(\mathrm{KG}(n,k))=n-2k+2
$$
である。下界を言い換えると、$n\ge2k$ のとき、$\binom{[n]}{k}$ を $n-2k+1$ 個の部分集合に分けると、どれかの部分集合は互いに交わらない 2 つの $k$ 元集合を含む。
$n=2k-1$ のときは ex-kn-small の 2 により辺がないので $\chi=1=n-2k+2$ であり、主張の中身は $n\ge2k$ の場合にある。主張は MZ04 p. 5 の形（$n\ge2k>0$）である。上界は prop-kn-upper で、下界は prf-kn-lower で証明する。
上界：塗り方の構成
$k\ge1$、$n\ge2k-1$ のとき、$\chi(\mathrm{KG}(n,k))\le n-2k+2$ である。
$m:=n-2k+2\ge1$ とおく。$S\in\binom{[n]}{k}$ に色
$$
c(S):=\min\bigl\{\min S,\ m\bigr\}\in\{1,\dots,m\}
$$
を与える。これが彩色であることを示す。$c(S)=c(T)=i$ とする。$i< m$ なら $\min S=\min T=i$ なので $i\in S\cap T$ である。$i=m$ なら $\min S\ge m$ かつ $\min T\ge m$ なので、$S,T$ はともに $\{m,m+1,\dots,n\}$ の部分集合であり、この集合の元の個数は $n-m+1=2k-1$ である。$\lvert S\rvert+\lvert T\rvert=2k>2k-1$ なので $S\cap T\neq\emptyset$ である。どちらの場合も $S,T$ は隣接しないので、$c$ は $m$-頂点彩色である。$\square$
この塗り方は、最小元が $1,\dots,n-2k+1$ の集合をその最小元の色で塗り、残りの集合（$2k-1$ 元集合 $\{n-2k+2,\dots,n\}$ の $k$ 元部分集合）をまとめて最後の色で塗るものである。MZ04 p. 2 は、上界が貪欲な塗り方で示せることを述べている。
下界：Greene の証明
下界の証明には、Borsuk–Ulamの定理 を球面の被覆の言葉に直した次の補題を使う。$S^d:=\{x\in\mathbb{R}^{d+1}\mid\lvert x\rvert=1\}$ とし（n次元球面）、$\langle\cdot,\cdot\rangle$ を標準内積とする。
$d\ge1$ とし、$U_1,\dots,U_d$ を $S^d$ の開集合、$F:=S^d\setminus(U_1\cup\cdots\cup U_d)$ とする。このとき、$U_1,\dots,U_d,F$ のどれかは対蹠点の組 $\{x,-x\}$ を含む。
ある $U_i$ が $S^d$ 全体なら、それが対蹠点の組を含む。そうでないとき、各 $i$ について
$$
f_i(x):=\inf\{\lvert x-y\rvert\mid y\in S^d\setminus U_i\}
$$
とおく。$\lvert f_i(x)-f_i(x')\rvert\le\lvert x-x'\rvert$ なので $f_i$ は連続であり、$S^d\setminus U_i$ は閉集合なので、$f_i(x)>0\iff x\in U_i$ である。$f:=(f_1,\dots,f_d)\colon S^d\to\mathbb{R}^d$ は連続なので、Borsuk–Ulamの定理 の記事の定理「Borsuk–Ulamの定理」（$n=d\ge1$ の場合）により、$f(x)=f(-x)$ となる $x\in S^d$ がある。ある $i$ で $f_i(x)>0$ なら $f_i(-x)=f_i(x)>0$ なので、$x,-x\in U_i$ である。すべての $i$ で $f_i(x)=f_i(-x)=0$ なら、$x$ と $-x$ はどの $U_i$ にも属さないので、$x,-x\in F$ である。$\square$
$S^d$ を $d+1$ 個の開集合 $U_1,\dots,U_{d+1}$ で覆うと、どれかが対蹠点の組を含む。$F\subset U_{d+1}$ なので、これは lem-kn-covering から従う。この形は Lyusternik–Schnirelmann の定理と呼ばれる（MZ04 p. 15）。$d=2$ で 3 つの閉集合で覆う場合は Borsuk–Ulamの定理 の記事の系「3 つの閉集合による被覆」にある。
次に、点を球面の上に「一般の位置」に置く。$x\in S^d$ について、$H(x):=\{y\in S^d\mid\langle x,y\rangle>0\}$ を $x$ を中心とする開半球といい、$E(x):=\{y\in S^d\mid\langle x,y\rangle=0\}$ をその境界の大円（$d-1$ 次元の球面）という。$S^d=H(x)\sqcup E(x)\sqcup H(-x)$ である。
$d\ge1$、$n\ge d+1$ とする。$S^d$ の相異なる $n$ 点 $v_1,\dots,v_n$ で、どの $x\in S^d$ についても $E(x)$ が高々 $d$ 個の $v_j$ しか含まないものがある。
相異なる実数 $t_1,\dots,t_n$ をとり、$\gamma(t):=(1,t,t^2,\dots,t^d)\in\mathbb{R}^{d+1}$、$v_j:=\gamma(t_j)/\lvert\gamma(t_j)\rvert$ とおく。$\gamma(t_j)$ の第 1 成分は $1$ なので、$v_j=v_l$ なら $\gamma(t_j)=\gamma(t_l)$、$t_j=t_l$ となり、$v_j$ は相異なる。どの $d+1$ 個の添字 $j_0< \cdots< j_d$ についても、$\gamma(t_{j_0}),\dots,\gamma(t_{j_d})$ を並べた行列式は Vandermonde行列式 $\prod_{a< b}(t_{j_b}-t_{j_a})\neq0$ なので、$v_{j_0},\dots,v_{j_d}$ は一次独立である。一方 $E(x)$ は $d$ 次元の部分空間 $x^\perp$ に含まれ、$x^\perp$ は一次独立な $d+1$ 個のベクトルを含めない。よって $E(x)$ に入る $v_j$ は高々 $d$ 個である。$\square$
以上の 2 つの補題から、主定理の下界が従う。
$n\ge2k$ の場合に、$\mathrm{KG}(n,k)$ が $d:=n-2k+1\ (\ge1)$ 色で塗れないことを示す。$d$-頂点彩色 $c\colon\binom{[n]}{k}\to\{1,\dots,d\}$ があるとして矛盾を導く。$n\ge d+1$ なので、lem-kn-general-position の点 $v_1,\dots,v_n\in S^d$ をとり、元 $j\in[n]$ を点 $v_j$ と同一視する。$i=1,\dots,d$ について
$$
U_i:=\Bigl\{x\in S^d\ \Bigm|\ c(S)=i\text{ かつ }v_j\in H(x)\ (j\in S)\text{ となる }S\in\tbinom{[n]}{k}\text{ がある}\Bigr\}
$$
とおく。$U_i$ は開集合である。実際、$x\in U_i$ とその $S$ について、有限個の不等式 $\langle x,v_j\rangle>0$（$j\in S$）は $x$ の近くの点でも成り立つ。lem-kn-covering により、次のどちらかが起こる。
(a) ある $i$ について $x,-x\in U_i$。このとき $c(S)=c(T)=i$ で、$S$ の点は $H(x)$ に、$T$ の点は $H(-x)$ に入るものがある。$H(x)\cap H(-x)=\emptyset$ で $v_j$ は相異なるので $S\cap T=\emptyset$、つまり $S$ と $T$ は隣接するのに同じ色である。これは $c$ が彩色であることに反する。
(b) $x,-x\in F$。$H(x)$ が $k$ 個以上の $v_j$ を含めば、そのうち $k$ 個の添字の集合 $S$ の色 $i=c(S)$ について $x\in U_i$ となるので、$x\in F$ より $H(x)$ に入る点は高々 $k-1$ 個である。$-x\in F$ から、$H(-x)$ に入る点も高々 $k-1$ 個である。$S^d=H(x)\sqcup E(x)\sqcup H(-x)$ なので、$E(x)$ には $n-2(k-1)=d+1$ 個以上の点が入る。これは lem-kn-general-position に反する。
どちらも矛盾なので、$\chi(\mathrm{KG}(n,k))\ge d+1=n-2k+2$ である。prop-kn-upper と合わせて thm-kn-main が成り立つ。$\square$
証明の中で、隣接する頂点の色が違うことを使うのは (a) だけで、(b) は点の配置だけで矛盾する。球面の次元 $d=n-2k+1$ は、(b) で「境界の大円に $d+1$ 点が乗る」ことがちょうど一般の位置に反するように選んである。MZ04 p. 9 は、Greene の仕事が、Borsuk–Ulam の定理の適当な形への短い幾何的な帰着を与え、Kneser 予想の自己完結した証明として最も短いものになっていると述べている。
例
$n=5$、$k=2$ では $n-2k+2=3$ である。prop-kn-upper の塗り方は、$\{1,2\},\{1,3\},\{1,4\},\{1,5\}$ に色 $1$、$\{2,3\},\{2,4\},\{2,5\}$ に色 $2$、$\{3,4\},\{3,5\},\{4,5\}$ に色 $3$ を与える。これは Petersenグラフ の記事の命題「Petersen グラフの彩色数」の証明の塗り方と同じである。下界は、そこでは長さ $5$ の奇閉路（たとえば $\{1,2\},\{3,4\},\{5,1\},\{2,3\},\{4,5\}$ を順に結ぶ閉路）から得ている。prf-kn-lower では $d=2$ で、5 点を $S^2$ に置き、どの大円にも 3 点が乗らないようにする。
$k\ge2$ では、奇閉路やクリークだけでは下界が足りなくなる。
$k\ge1$、$n=3k-1$ とする。互いに交わらない 3 つの $k$ 元集合は $3k$ 個の元を要するので、$\mathrm{KG}(3k-1,k)$ は三角形を含まず、$\omega=2$ である（$3k-1\ge2k$ なので辺はある）。一方 thm-kn-main により $\chi(\mathrm{KG}(3k-1,k))=k+1$ である。$k=3$ の $\mathrm{KG}(8,3)$ は、56 頂点・三角形なしで彩色数 $4$ のグラフになる。彩色数 の記事の注意「三角形を含まないグラフの彩色数」が述べる現象の、具体的な例の一つである（MZ04 p. 2）。
一般に、クリークと独立集合からの下界は次のように小さい。
$k\ge1$、$n\ge k$、$N:=\binom nk$ とする。
- $\omega(\mathrm{KG}(n,k))=\lfloor n/k\rfloor$ である。
- $\alpha(\mathrm{KG}(n,k))\ge\binom{n-1}{k-1}$ であり、したがって下界 $\chi\ge N/\alpha$ の右辺は $n/k$ 以下である。
1：クリークは互いに交わらない $k$ 元集合の族なので、その個数を $r$ とすると $rk\le n$、$r\le\lfloor n/k\rfloor$ である。$\{1,\dots,k\},\{k+1,\dots,2k\},\dots$ と $\lfloor n/k\rfloor$ 個並べれば等号が成り立つ。2：$1$ を含む $k$ 元集合の全体はどの 2 つも $1$ を共有するので独立集合で、その個数は $\binom{n-1}{k-1}$ である。よって $N/\alpha\le\binom nk\big/\binom{n-1}{k-1}=n/k$ である。$\square$
$n\ge2k$ では 2 の不等式は等号になる。交わる $k$ 元集合の族の大きさは $\binom{n-1}{k-1}$ 以下だからである（Erdős–Ko–Radoの定理）。
| グラフ | $\omega$ | $N/\alpha$ の上限 | $\chi$ |
|---|---|---|---|
| $\mathrm{KG}(n,1)=K_n$ | $n$ | $n$ | $n$ |
| $\mathrm{KG}(2k,k)$（$k\ge1$） | $2$ | $2$ | $2$ |
| $\mathrm{KG}(5,2)$ | $2$ | $5/2$ | $3$ |
| $\mathrm{KG}(8,3)$ | $2$ | $8/3$ | $4$ |
| $\mathrm{KG}(3k-1,k)$ | $2$ | $(3k-1)/k<3$ | $k+1$ |
| $\mathrm{KG}(n,k)$（$n\ge2k$） | $\lfloor n/k\rfloor$ | $n/k$ | $n-2k+2$ |
$n=3k-1$ として $k$ を大きくすると、$\omega$ と $N/\alpha$ は $3$ 未満に留まるのに、$\chi=k+1$ はいくらでも大きくなる。この差を埋めたのが位相的な下界である（MZ04 p. 2）。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $n\ge2k-1$ | $\mathrm{KG}(4,3)$ | 等式 $\chi=n-2k+2$ |
| lem-kn-covering の開集合の個数が $d$ 以下であること | $S^1$ の 3 つの開いた弧 | 対蹠点の組を含む集合の存在 |
| prf-kn-lower の点が一般の位置にあること | $S^1$ の 4 点 $(\pm1,0)$、$(0,\pm1)$ | prf-kn-lower の (b) の矛盾 |
1 行目：$\mathrm{KG}(4,3)$ は 4 頂点で、ex-kn-small の 2 により辺がないので $\chi=1$ である。一方 $n-2k+2=0$ である。$n<2k-1$ では辺のないグラフでも頂点は残るので、等式は成り立たない。
2 行目：$d=1$ とし、$S^1$ を角度で表して、$U_1,U_2,U_3$ を中心角 $0,\frac{2\pi}3,\frac{4\pi}3$、長さ $\frac{2\pi}{3}+\frac{\pi}{6}$ の開いた弧とする。3 つの弧は $S^1$ を覆い、どれも長さが $\pi$ より短いので対蹠点の組を含まない。$U_1,U_2$ を $d+1=2$ 個の開集合とすると、$F=S^1\setminus(U_1\cup U_2)$ は $U_3$ に含まれるので、やはり対蹠点の組を含まない。開集合を $d$ 個から 1 つ増やすと、lem-kn-covering の結論は成り立たない。
3 行目：$n=4$、$k=2$、$d=1$ とし、$v_1=(1,0)$、$v_2=(-1,0)$、$v_3=(0,1)$、$v_4=(0,-1)$ とおく。$x=(0,1)$ では $E(x)=\{(\pm1,0)\}$ が $d+1=2$ 点 $v_1,v_2$ を含み、$H(x)$ と $H(-x)$ は $v_3$、$v_4$ を 1 点ずつ含む。よって $x,-x\in F$ となりうるが、lem-kn-general-position が使えないので (b) は矛盾にならない。$\mathrm{KG}(4,2)$ 自体は完全マッチングで $\chi=2$ であり、崩れるのは証明の一段である。
補足
- 名前：Kneserの定理(加法的組合せ論)（アーベル群の部分集合の和の集合 $A+B$ の大きさ）は加法的組合せ論の定理で、この記事の主張とは別である。Lovász の名を冠する定理もほかに多い（Lovászの局所補題 など）。
- 歴史と別証明：Kneser は 1955 年に Jahresbericht der DMV の問題として、$\chi\ge n-2k+\text{定数}$ の証明を求め、等号 $\chi=n-2k+2$ を予想した（上界は prop-kn-upper のように易しい）。Lovász は 1978 年に、グラフから作る単体複体（近傍複体）の位相で彩色数を下から評価する方法を作って予想を解いた。その後 Bárány、Schrijver、Dol'nikov、Sarkaria、Kříž、Greene らの証明が現れ、いずれも Borsuk–Ulam の定理の何らかの形に基づく（MZ04 pp. 1–2）。Bárány の証明は、$S^d$ の上に $2k+d$ 点を、どの開半球も $k$ 点以上を含むように置けるという Gale の補題を使う（MZ04 p. 8）。
- 組合せ的な証明：Matoušek は、Borsuk–Ulam の定理の組合せ的な対応物である Tuckerの補題 を使い、位相を使わない証明を与えた（dLZ05 pp. 1–2）。
- Schrijver グラフ：$0<2k< n$ とし、$[n]$ を円周に並べたとき隣り合う 2 元を含まない $k$ 元集合だけを頂点とする $\mathrm{KG}(n,k)$ の誘導部分グラフを $\mathrm{SG}(n,k)$ と書く。Schrijver は $\chi(\mathrm{SG}(n,k))=n-2k+2$ であり、どの頂点を除いても彩色数が下がることを示した（MZ04 p. 15。この記事では証明しない）。
- 一般のグラフへ：どの有限グラフも、適当な集合族の「交わらない 2 つを結ぶ」グラフとして表せるので、Kneser 予想の証明の方法は一般のグラフの彩色数の下界を与える（MZ04 pp. 1, 5）。
関連項目
- 前提: Kneserグラフ, 彩色数, Borsuk–Ulamの定理, n次元球面
- 例: Petersenグラフ, 完全グラフ
- 比較: Tuckerの補題, Erdős–Ko–Radoの定理, クリーク数, 独立集合(グラフ)
- 発展: Vandermonde行列式
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
