クネーザーグラフのソースを表示

{{infobox graph
 | name = クネーザーグラフ
 | image = [[File:Kneser graph KG(5,2).svg|230px]]
 | image_caption = クネーザーグラフ {{math|''KG''<sub>5,2</sub>}}<br/>（[[ピーターセングラフ]]と同型）
 | namesake = [[マルティン・クネーザー]]
 | vertices = <math>\textstyle\binom{n}{k}</math>
 | edges = <math>\textstyle\binom{n}{k} \binom{n - k}{k} / 2</math>
 | chromatic_number = <math>\left\{\begin{array}{ll}n - 2 k + 2 & n \ge 2 k\\ 1 & \text{otherwise}\end{array}\right.</math>
 | properties = [[正則グラフ|<math>\textstyle\binom{n - k}{k}</math>-正則]]<br/>[[対称グラフ|弧推移的]]
 |notation = {{math|''KG''<sub>''n'',''k''</sub>}}, {{math|''K''(''n'',''k'')}} 
}}

[[数学]]の[[グラフ理論]]における'''クネーザーグラフ'''（{{Lang-en-short|Kneser graph}}） {{math|''KG''<sub>''n'',''k''</sub>}} とは、''n'' 元集合の''k''元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究した[[マルティン・クネーザー]]の名にちなむ。

== 例 ==
''n'' 個の頂点を持つ[[完全グラフ]]はクネーザーグラフ {{math|''KG''<sub>''n'',1</sub>}} である。

クネーザーグラフ {{math|''KG''<sub>2''n'' &minus; 1,''n'' &minus; 1</sub>}} は{{仮リンク|奇グラフ|en|odd graph}} {{math|''O<sub>n</sub>''}} として知られる。奇グラフ {{math|1=''O''<sub>3</sub> = ''KG''<sub>5,2</sub>}} は[[ピーターセングラフ]]と同型である。

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

* {{harvtxt|Kneser|1955}}が予想したように、クネーザーグラフ {{math|''KG''<sub>''n'',''k''</sub>}} の[[グラフ彩色|彩色数]]は必ず {{math|''n'' &minus; 2''k'' + 2}} となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。{{harvs|authorlink=:en:László Lovász|first=László|last=Lovász|year=1978|txt}} はこの事実を、{{仮リンク|位相的組合せ論|en|topological combinatorics}}の分野における位相的手法を用いることによって証明した。その後まもなく、{{harvs|authorlink=:en:Imre Bárány|first=Imre|last=Bárány|year=1978|txt}} は{{仮リンク|ボルサック-ウラムの定理|en|Borsuk–Ulam theorem}}と[[デヴィッド・ゲール]]の補題を用いることによって、簡単な証明を与え、さらに {{harvtxt|Greene|2002}} は簡略化ではあるが依然として位相的な証明を与えることによって{{仮リンク|モーガン賞|en|Morgan Prize}}を得た。また、{{harvtxt|Matoušek|2004}} は純粋な{{仮リンク|組合せ論的証明|en|combinatorial proof}}を与えた。
* {{math|''n'' ≥ 3''k''}} であるなら、クネーザーグラフは常に[[ハミルトン路|ハミルトン閉路]]を含む {{harv|Chen|2000}}。計算機的な研究によれば、{{math|''n'' ≤ 27}} であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである {{harv|Shields|2004}}。
* {{math|''n'' < 3''k''}}であるなら、クネーザーグラフは三角形を含まない。より一般的に、{{math|''n'' ≥ 2''k'' + 2}} であればクネーザーグラフは常に長さ4の閉路を含むが、{{math|2''k''}} に近い値 ''n'' に対して、最も短い奇閉路は一定の長さを持たないことがある {{harv|Denley|1997}}。
* 連結クネーザーグラフ {{math|''KG''<sub>''n'',''k''</sub>}} の[[距離|直径]]{{enlink|distance (graph theory)}}は
*:<math>\left\lceil \frac{k-1}{n-2k} \right\rceil + 1</math>  {{harv|Valencia-Pabon|Vera|2005}}
:である。
* クネーザーグラフ {{math|''KG''<sub>''n'',''k''</sub>}} の[[スペクトルグラフ理論|グラフスペクトル]]は次のように与えられる:
: <math>j=0,...,k</math> に対し、[[固有値]] <math>\lambda_j=(-1)^j\binom{n-k-j}{k-j}</math> が得られる。ここで、その[[重複度]]は、<math> j > 0</math> に対しては <math>\binom{n}{j}-\binom{n}{j-1}</math> であり、<math>j = 0 </math> に対しては 1 となる。証明には[http://www.math.caltech.edu/~2011-12/2term/ma192b/kneser-evals.pdf この論文]を参照されたい。

== 関連するグラフ ==
{{仮リンク|ジョンソングラフ|en|Johnson graph}}は、''n'' 元集合の ''k'' 元部分集合が頂点となり、その {{math|(''k''&nbsp;&minus;&nbsp;1)}}-元部分集合が一致するとき、各頂点が隣接するようなグラフである。{{math|1=''k'' = 2}} に対して、ジョンソングラフはクネーザーグラフ {{math|''KG''<sub>''n'',2</sub>}} の[[補グラフ|補]]となる。ジョンソングラフは、{{仮リンク|ジョンソンスキーム|en|Johnson scheme}}と密接に関係している。それらはいずれも{{仮リンク|セルマー・ジョンソン|en|Selmer M. Johnson}}の名にちなむ。

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

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

2部クネーザーグラフは、{{math|''KG''<sub>''n'',''k''</sub>}} の{{仮リンク|2部二重被覆|en|bipartite double cover}}として構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている {{harv|Simpson|1991}}。2部クネーザーグラフ  {{math|''H''<sub>5,2</sub>}} は{{仮リンク|デザルググラフ|en|Desargues graph}}であり、2部クネーザーグラフ {{math|''H''<sub>''n'',1</sub>}} は{{仮リンク|王冠グラフ|en|crown graph}}である。

== 参考文献 ==
* {{citation
  | doi = 10.1016/0097-3165(78)90023-7
  | mr = 0514626
  | last = Bárány | first = Imre 
  | authorlink = :en:Imre Bárány
  | journal = [[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]] | series = Series A
  | title = A short proof of Kneser's conjecture
  | volume = 25
  | issue = 3 
  | year = 1978 
  | pages = 325–326}}.
* {{citation
  | last = Chen | first = Ya-Chen
  | journal = [[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]] | series = Series B
  | title = Kneser graphs are Hamiltonian for {{math|''n'' ≥ 3''k''}}
  | volume = 80
  | issue = 1
  | year = 2000
  | pages = 69–79
  | url = http://math.la.asu.edu/~cchen/kneser.ps
  | doi = 10.1006/jctb.2000.1969
  | mr = 1778200}}.
* {{citation
  | title = The odd girth of the generalised Kneser graph
  | last = Denley | first = Tristan
  | journal = [[:en:European Journal of Combinatorics|European Journal of Combinatorics]]
  | volume = 18
  | issue = 6
  | year = 1997
  | pages = 607–611
  | doi = 10.1006/eujc.1996.0122
  | mr = 1468332}}.
* {{citation
  | last = Greene |first=Joshua E.
  | title = A new short proof of Kneser's conjecture
  | journal = [[:en:American Mathematical Monthly|American Mathematical Monthly]]
  | year = 2002
  | volume = 109
  | issue = 10
  | pages = 918–920
  | doi = 10.2307/3072460
  | mr = 1941810}}.
* {{citation
  | last = Kneser | first = Martin | authorlink = マルティン・クネーザー
  | title = Aufgabe 360
  | journal = Jahresbericht der Deutschen Mathematiker-Vereinigung | series = 2. Abteilung
  | volume = 58
  | year = 1955
  | pages = 27}}.
* {{citation
  | last = Lovász | first = László
  | authorlink = :en:László Lovász
  | title = Kneser's conjecture, chromatic number, and homotopy
  | year = 1978
  | volume = 25
  | journal = [[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]] | series = Series A
  | issue = 3
  | pages = 319–324
  | doi = 10.1016/0097-3165(78)90022-5
  | mr = 0514625}}.
* {{citation
  | last = Matoušek | first = Jiří | authorlink = :en:Jiří Matoušek (mathematician)
  | title = A combinatorial proof of Kneser's conjecture
  | journal = [[:en:Combinatorica|Combinatorica]]
  | volume = 24
  | issue = 1
  | year = 2004
  | pages = 163–170
  | doi = 10.1007/s00493-004-0011-1
  | mr = 2057690}}.
* {{citation
  | last = Shields | first = Ian Beaumont
  | title = Hamilton Cycle Heuristics in Hard Graphs
  | series = Ph.D. thesis
  | publisher = [[ノースカロライナ州立大学|North Carolina State University]]
  | url = http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/
  | year = 2004}}.
* {{citation
  | last = Simpson | first = J. E.
  | contribution = Hamiltonian bipartite graphs
  | title = Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991)
  | pages = 97–110
  | series = Congressus Numerantium
  | volume = 85
  | year = 1991
  | mr = 1152123}}.
* {{citation
  | title = On the diameter of Kneser graphs
  | last1 = Valencia-Pabon | first1 = Mario | last2 = Vera | first2 = Juan-Carlos
  | journal = [[:en:Discrete Mathematics (journal)|Discrete Mathematics]]
  | volume = 305
  | issue = 1–3
  | pages = 383–385
  | year = 2005
  | doi = 10.1016/j.disc.2005.10.001
  | mr = 2186709}}.

== 外部リンク ==
* {{MathWorld|urlname=KneserGraph|title=Kneser Graph}}
* {{MathWorld|urlname=OddGraph|title=Odd Graph}}

{{DEFAULTSORT:くねえさあくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]