クネーザーグラフ

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

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

例

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

クネーザーグラフ KG_{2n − 1,n − 1} は奇グラフ（英語版） O_n として知られる。奇グラフ O₃ = KG_5,2 はピーターセングラフと同型である。

性質

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

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

  ${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1}$ (Valencia-Pabon & Vera 2005)

である。

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

${\displaystyle j=0,...,k}$ に対し、固有値 ${\displaystyle \lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}}}$ が得られる。ここで、その重複度は、${\displaystyle j>0}$ に対しては ${\displaystyle {\binom {n}{j}}-{\binom {n}{j-1}}}$ であり、${\displaystyle j=0}$ に対しては 1 となる。証明にはこの論文を参照されたい。

関連するグラフ

ジョンソングラフ（英語版）は、n 元集合の k 元部分集合が頂点となり、その (k − 1)-元部分集合が一致するとき、各頂点が隣接するようなグラフである。k = 2 に対して、ジョンソングラフはクネーザーグラフ KG_n,2 の補となる。ジョンソングラフは、ジョンソンスキーム（英語版）と密接に関係している。それらはいずれもセルマー・ジョンソン（英語版）の名にちなむ。

一般化クネーザーグラフ KG_n,k,s とは、クネーザーグラフと頂点集合は同じものであるが、二つの頂点が連結するための必要十分条件が、それらに対応する集合が s 以下の共通部分を持つこと、であるようなグラフのことである (Denley 1997)。したがって、KG_n,k,0 = KG_n,k である。

2部クネーザーグラフ （bipartite Kneser graph）H_n,k は、n 個の元の集まりから抽出される k 個の元および n − k 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 ${\displaystyle \textstyle {\binom {n-k}{k}}}$ でもって頂点推移的である。

2部クネーザーグラフは、KG_n,k の2部二重被覆（英語版）として構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている (Simpson 1991)。2部クネーザーグラフ H_5,2 はデザルググラフ（英語版）であり、2部クネーザーグラフ H_n,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, MR0514626.
• Chen, Ya-Chen (2000), “Kneser graphs are Hamiltonian for n ≥ 3k”, Journal of Combinatorial Theory, Series B 80 (1): 69–79, doi:10.1006/jctb.2000.1969, MR1778200, http://math.la.asu.edu/~cchen/kneser.ps.
• 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, http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/.
• 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 (英語).