ジョンソングラフ

ジョンソングラフ
ジョンソングラフJ (5,2)
名前の由来	セルマー・M・ジョンソン
頂点	${\displaystyle {\binom {n}{k}}}$
エッジ	${\displaystyle {\frac {1}{2}}k(nk){\binom {n}{k}}}$
直径	${\displaystyle \min(k,nk)}$
プロパティ	${\displaystyle k(nk)}$-正則 頂点推移 距離推移 ハミルトン連結
表記	${\displaystyle J(n,k)}$
グラフとパラメータの表

数学において、ジョンソングラフは集合のシステムから定義される無向グラフの特別なクラスである。ジョンソングラフの頂点は要素集合の要素部分集合である。2つの頂点（部分集合）の交差に要素が含まれる場合、2つの頂点は隣接している。^[1]ジョンソングラフと密接に関連するジョンソンスキームは、セルマー・M・ジョンソンにちなんで名付けられている。 ${\displaystyle J(n,k)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle (k-1)}$

• と は両方とも完全グラフK _nです。${\displaystyle J(n,1)}$${\displaystyle J(n,n-1)}$
• ${\displaystyle J(4,2)}$八面体グラフです。
• ${\displaystyle J(5,2)}$はピーターセングラフの補グラフであり、^[1] K ₅の線グラフである。より一般的には、すべての に対して、ジョンソングラフはK _nの線グラフであり、クネザーグラフの補グラフである。${\displaystyle n}$${\displaystyle J(n,2)}$ ${\displaystyle K(n,2).}$

• ${\displaystyle J(n,k)}$は同型である${\displaystyle J(n,nk).}$
• すべての について、距離にある任意の頂点のペアは共通の要素を共有します。${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$${\displaystyle j}$${\displaystyle kj}$
• ${\displaystyle J(n,k)}$はハミルトン連結であり、すべての頂点ペアがグラフ内のハミルトン経路の終点を形成することを意味する。特に、これはハミルトン閉路を持つことを意味する。^[2]
• ジョンソングラフは頂点連結であることも知られている。^[3]${\displaystyle J(n,k)}$${\displaystyle k(nk)}$
• ${\displaystyle J(n,k)}$は、( n  −1)次元多面体の頂点と辺のグラフを形成し、これを超単体と呼ぶ。^[4]
• のクリーク数は、最小の固有値と最大の固有値を用いた式で与えられます。${\displaystyle J(n,k)}$${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }.}$
• の彩色数は最大で^{[5]である。}${\displaystyle J(n,k)}$${\displaystyle n,\chi (J(n,k))\leq n.}$
• 各ジョンソングラフは局所的にグリッドであり、任意の頂点の近傍の誘導サブグラフはルークのグラフであることを意味する。より正確には、ジョンソングラフでは、各近傍はルークのグラフである。^[6]${\displaystyle J(n,k)}$${\displaystyle k\times (nk)}$

の距離推移的 部分群はと同型である。実際、のときを除いて である。[ ^7]${\displaystyle \operatorname {Aut} (J(n,k))}$ ${\displaystyle \operatorname {Sym} (n)}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$${\displaystyle n=2k\geq 4}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$

距離推移的であることの結果として、は距離正則でもある。をその直径とすると、 の交差配列は次のように与えられる。 ${\displaystyle J(n,k)}$${\displaystyle d}$${\displaystyle J(n,k)}$

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

どこ：

${\displaystyle {\begin{aligned}b_{j}&=(kj)(nkj)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}}$

がでない限り、その交差配列は他のどの異なる距離正則グラフとも共有されないことがわかります。の交差配列は、ジョンソングラフではない他の3つの距離正則グラフと共有されます。^[1]${\displaystyle J(n,k)}$${\displaystyle J(8,2)}$${\displaystyle J(8,2)}$

• の特性多項式は次のように与えられる。${\displaystyle J(n,k)}$

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right )^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

ここで^[7]${\displaystyle A_{n,k}(j)=(kj)(nkj)-j.}$

• の固有ベクトルは明示的に記述される。^[8]${\displaystyle J(n,k)}$

ジョンソングラフはジョンソンスキームと密接に関連しており、ジョンソンスキームはk要素セットの各ペアに、 2つのセットの対称差の半分のサイズの数値が関連付けられる関連付けスキームです。 ^{[9]ジョンソングラフは、関連付けスキームで距離1にあるセットのペアごとにエッジを持ち、関連付けスキームの距離はジョンソングラフの}最短パス距離とまったく同じです。^[10]${\displaystyle J(n,k)}$

ジョンソンスキームは、別の距離推移グラフファミリーである奇数グラフとも関連しており、その頂点は-要素集合の-要素部分集合であり、辺は互いに素な部分集合のペアに対応する。^[9]${\displaystyle k}$${\displaystyle (2k+1)}$

ジョンソングラフの頂点拡張特性や、与えられたサイズの対応する頂点の極値集合の構造は、まだ完全には解明されていない。しかし、最近、大規模な頂点集合の拡張に関する漸近的に厳密な下限が得られている。^[11]

一般に、ジョンソングラフの彩色数を決定することは未解決の問題である。^[12]

• グラスマングラフ

• ワイスタイン、エリック W.、「ジョンソン グラフ」、MathWorld
• Brouwer、Andries E.、ジョンソングラフ