クネザーグラフ

クネザーグラフ
クネザーグラフK (5, 2)はピーターセングラフと 同型である。
名前の由来	マーティン・クネザー
頂点	${\displaystyle {\binom {n}{k}}}$
エッジ	${\displaystyle {\frac {1}{2}}{\binom {n}{k}}{\binom {nk}{k}}}$
彩度数	${\displaystyle {\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}}$
プロパティ	${\displaystyle {\tbinom {nk}{k}}}$-正規 弧-推移
表記	K ( n、k )、KG n、k。
グラフとパラメータの表

グラフ理論において、クネーザーグラフ K ( n , k ) (またはKG _{n , k} ) は、頂点がn個の要素の集合のk個の要素の部分集合に対応し、2 つの頂点が隣接するのは、対応する 2 つの集合が互いに素である場合に限ります。クネーザーグラフは、1956 年に初めて研究したMartin Kneserにちなんで名付けられました。

クネザーグラフK ( n ,1)はn頂点の完全グラフです。

クネーザーグラフK ( n ,2)は、 n頂点の完全グラフの線グラフの補グラフです。

クネザーグラフK (2 n − 1, n − 1)は奇グラフ O _nである。特にO ₃ = K (5, 2)はピーターセングラフである（右上の図を参照）。

クネザーグラフO ₄ = K (7, 3)は右側に視覚化されています。

Kneser グラフには頂点があります。各頂点にはちょうど隣接する頂点があります。 ${\displaystyle K(n,k)}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {nk}{k}}}$

クネザーグラフは頂点推移的かつ弧推移的です。 のとき、クネザーグラフはパラメータ を持つ強正則グラフです。 しかし、 のときは強正則ではありません。これは、隣接していない頂点の異なるペアが、対応する集合の 交差のサイズに応じて異なる数の共通近傍を持つためです。${\displaystyle k=2}$${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{ 2}})}$${\displaystyle k>2}$

クネザーグラフは正則かつ辺推移的であるため、 が切断されている場合を除き、その頂点の接続性は次数に等しくなります。より正確には、 の接続性は頂点あたりの近傍数と同じです。 ^[1]${\displaystyle K(2k,k)}$${\displaystyle K(n,k)}$${\displaystyle {\tbinom {nk}{k}},}$

Kneser (1956)が予想したように、に対するKneser グラフの彩色数はちょうどn − 2 k + 2である。たとえば、Petersen グラフでは、任意の適切な彩色に 3 つの色が必要である。この予想はいくつかの方法で証明された。 ${\displaystyle K(n,k)}$${\displaystyle n\geq 2k}$

• 1978年にラースロー・ロヴァースは位相幾何学的手法を用いてこれを証明し、^[2]位相的組合せ論という分野を生み出した。
• その後すぐに、イムレ・バラニはボルスク・ウラム定理とデイヴィッド・ゲイルの補題を用いて簡単な証明を与えた。^[3]
• ジョシュア・E・グリーンは、さらに簡略化されたが依然として位相的な証明により、2002年の優れた学部生研究に対するモーガン賞を受賞した。 ^[4]
• 2004 年に、イジー・マトウシェクは純粋に組み合わせによる証明を発見しました。^[5]

対照的に、これらのグラフの分数彩色数は である。^[6] のとき、には辺がなく、その彩色数は 1 である。 ${\displaystyle n/k}$${\displaystyle n<2k}$${\displaystyle K(n,k)}$

ピーターセングラフがハミルトングラフではないことはよく知られていますが、これが唯一の例外であり、他のすべての連結されたクネーザーグラフK ( n , k )はハミルトングラフであると長い間推測されていました。

2003年にチェンは、クネザーグラフK ( n , k )がハミルトン閉路を含むことを示した。^[7]

${\displaystyle n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).}$

以来

${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1}$

すべてに当てはまる場合、この条件は満たされます ${\displaystyle k}$

${\displaystyle n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.}$

同じ頃、シールズはピーターセングラフを除いて、n≤27の連結クネザーグラフK(n,k)はすべてハミルトングラフであることを（計算的に）示した。 [ 8 ^]

2021年、ミュッツェ、ヌメンパロ、ワルチャクは、負でない整数が存在する場合、クネザーグラフK ( n , k )にハミルトン閉路が含まれることを証明した。^[9]特に、奇グラフOn_には、 n≥4の場合にはハミルトン閉路が含まれる。最終的に、2023年にメリノ、ミュッツェ、ナムラタがこの予想の証明を完了した。^[10] ${\displaystyle a}$${\displaystyle n=2k+2^{a}}$

n < 3 kのとき、クネザーグラフK ( n , k )には三角形が含まれません。より一般的には、n < ck のときはサイズcのクリークは含まれませんが、 n ≥ ckのときはそのようなクリークが含まれます。さらに、 n ≥ 2 k + 2 のときは常にクネザーグラフに長さ 4 のサイクルが含まれますが、 nの値が2 kに近い場合、最短の奇数サイクルの長さは可変になることがあります。^[11]

連結クネーザーグラフK ( n , k )の直径は[ 12 ^] $${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$$

クネザーグラフK ( n , k )のスペクトルはk +1個の異なる固有値から構成される。 さらに、は重複度1で発生し、重複度は1である。^[13]$${\displaystyle \lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots ,k.}$$${\displaystyle \lambda_{j}}$ ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$${\displaystyle j>0}$${\displaystyle \lambda_{0}}$

エルデシュ・コー・ラドの定理によれば、クネーザーグラフ K ( n , k )の独立数は${\displaystyle n\geq 2k}$$${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}}.}$$

ジョンソングラフ J ( n , k )は、頂点がn要素集合のk要素部分集合であるグラフであり、2つの頂点が( k  − 1)要素集合で出会うとき、それらの頂点は隣接している。ジョンソングラフJ ( n , 2) は、クネザーグラフK ( n , 2)の補グラフである。ジョンソングラフはジョンソンスキームと密接な関係があり、どちらもセルマー・M・ジョンソンにちなんで名付けられている。

一般化されたクネザーグラフ K ( n , k , s )はクネザーグラフK ( n , k )と同じ頂点集合を持ちますが、2つの頂点がs個以下の項目で交差する集合に対応するときは常にそれらの頂点を接続します。^[11]したがって、K ( n , k ,0) = K ( n , k )です。

二部クネザーグラフ H ( n , k ) は、 n個の要素のコレクションから抽出されたk 個とn − k 個のアイテムの集合を頂点として持ちます。 2 つの頂点は、一方の集合が他方の集合のサブセットである場合に、辺で接続されます。 クネザーグラフと同様に、次数で頂点推移的です。二部クネザーグラフは、K ( n , k )の二部二重被覆として形成でき、各頂点のコピーを 2 つ作成し、各辺を対応する頂点のペアを接続する辺のペアで置き換えます。^[14]二部クネザーグラフH (5, 2)はデザルググラフであり、二部クネザーグラフH ( n , 1)はクラウングラフです。 ${\displaystyle {\tbinom {n-k}{k}}.}$

• ワイスタイン、エリック・W.「クネーザーグラフ」。マスワールド。
• Weisstein、Eric W.「奇数グラフ」。MathWorld。