クネーザーグラフ

クネーザーグラフ
	クネーザーグラフ KG5,2; （ピーターセングラフと同型）
命名者	マルティン・クネーザー
頂点
辺
彩色数
特性	-正則; 弧推移的
表記	KGn,k, K(n,k)
	テンプレートを表示

数学のグラフ理論におけるクネーザーグラフ（英: Kneser graph） $KG n, k$ とは、n 元集合のk元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究したマルティン・クネーザーの名にちなむ。

例

n 個の頂点を持つ完全グラフはクネーザーグラフ $KG n,1$ である。

クネーザーグラフ $KG 2 n - 1, n - 1$ は奇グラフ（英語版） $O n$ として知られる。奇グラフ $O 3 = KG 5,2$ はピーターセングラフと同型である。

性質

クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず $\textstyle {\binom {n-k}{k}}$ 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。

Kneser (1955)が予想したように、クネーザーグラフ $KG n, k$ の彩色数は必ず $n - 2 k + 2$ となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。László Lovász (1978) はこの事実を、位相的組合せ論（英語版）の分野における位相的手法を用いることによって証明した。その後まもなく、Imre Bárány (1978) はボルサック-ウラムの定理（英語版）とデヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらに Greene (2002) は簡略化ではあるが依然として位相的な証明を与えることによってモーガン賞（英語版）を得た。また、Matoušek (2004) は純粋な組合せ論的証明（英語版）を与えた。
$n \geq 3 k$ であるなら、クネーザーグラフは常にハミルトン閉路を含む (Chen 2000)。計算機的な研究によれば、 $n \leq 27$ であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである (Shields 2004)。
$n < 3 k$ であるなら、クネーザーグラフは三角形を含まない。より一般的に、 $n \geq 2 k + 2$ であればクネーザーグラフは常に長さ4の閉路を含むが、 $2 k$ に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがある (Denley 1997)。
連結クネーザーグラフ $KG n, k$ の直径 (distance (graph theory)) は
$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1$ (Valencia-Pabon & Vera 2005)

である。

クネーザーグラフ $KG n, k$ のグラフスペクトルは次のように与えられる:

j=0,...,k

に対し、固有値

\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}}

が得られる。ここで、その重複度は、

j>0

に対しては

{\binom {n}{j}}-{\binom {n}{j-1}}

であり、

j=0

に対しては 1 となる。証明にはこの論文を参照されたい。

参考文献

Bárány, Imre (1978), “A short proof of Kneser's conjecture”, Journal of Combinatorial Theory, Series A 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, MR 0514626 .
Chen, Ya-Chen (2000), “Kneser graphs are Hamiltonian for $n \geq 3 k$ ”, Journal of Combinatorial Theory, Series B 80 (1): 69–79, doi:10.1006/jctb.2000.1969, MR1778200 .
Denley, Tristan (1997), “The odd girth of the generalised Kneser graph”, European Journal of Combinatorics 18 (6): 607–611, doi:10.1006/eujc.1996.0122, MR1468332 .
Greene, Joshua E. (2002), “A new short proof of Kneser's conjecture”, American Mathematical Monthly 109 (10): 918–920, doi:10.2307/3072460, MR1941810 .
Kneser, Martin (1955), “Aufgabe 360”, Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung 58: 27 .
Lovász, László (1978), “Kneser's conjecture, chromatic number, and homotopy”, Journal of Combinatorial Theory, Series A 25 (3): 319–324, doi:10.1016/0097-3165(78)90022-5, MR0514625 .
Matoušek, Jiří (2004), “A combinatorial proof of Kneser's conjecture”, Combinatorica 24 (1): 163–170, doi:10.1007/s00493-004-0011-1, MR2057690 .
Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, North Carolina State University .
Simpson, J. E. (1991), “Hamiltonian bipartite graphs”, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, 85, pp. 97–110, MR1152123 .
Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), “On the diameter of Kneser graphs”, Discrete Mathematics 305 (1–3): 383–385, doi:10.1016/j.disc.2005.10.001, MR2186709 .

外部リンク

Weisstein, Eric W. "Kneser Graph". mathworld.wolfram.com (英語).
Weisstein, Eric W. "Odd Graph". mathworld.wolfram.com (英語).

クネーザーグラフ

目次

例

性質

関連するグラフ

参考文献

外部リンク

クネーザーグラフ
クネーザーグラフ $KG 5,2$ （ピーターセングラフと同型）
命名者	マルティン・クネーザー
頂点	$\textstyle {\binom {n}{k}}$
辺	$\textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2$
彩色数	$\left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.$
特性	$\textstyle {\binom {n-k}{k}}$ -正則弧推移的
表記	$KG n, k$ , $K (n, k)$
テンプレートを表示