ジョンソングラフ

ジョンソングラフ
ジョンソングラフ
	ジョンソングラフJ (5,2)
名前の由来	セルマー・M・ジョンソン
頂点
エッジ
直径
プロパティ	-正則; 頂点推移; 距離推移; ハミルトン連結; 多面体
表記
	グラフとパラメータの表

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

特殊なケース

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

グラフ理論的性質

$J(n,k)$ は $J(n,n-k).$
すべてのについて、距離にある任意の頂点のペアは共通の要素を共有します。 $0\leq j\leq \operatorname {diam} (J(n,k))$ $j$ $k-j$
$J(n,k)$ はハミルトン連結であり、グラフ上のすべての頂点ペアがハミルトン路の端点を形成することを意味する。特に、これはグラフがハミルトン閉路を持つことを意味する。^[3]
ジョンソングラフは-頂点連結であることも知られている。^[4] $J(n,k)$ $k(n-k)$
$J(n,k)$ は（n −1）次元多面体の頂点-辺グラフを形成し、超単体と呼ばれる。^[5]
任意の極大クリークは、元部分集合およびに対してはの形式、に対してはの形式、またはエッジケースに対してはの形式のいずれかである。^[6] $\{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}$ $(k-1)$ $S$ $k<n-1$ $\{S\setminus \{x\}\mid x\in S\}$ $(k+1)$ $S$ $k>1$ $\{\{1\},\{2\}\}$ $(n,k)=(2,1)$
のクリーク数は、その最小および最大の固有値を用いた式で与えられる。または、上記の最大クリークの明示的な記述により、 $J(n,k)$ $\omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }$ $\omega (J(n,k))=\max\{k+1,N-k+1\}.$
のクリーク被覆数は、に対して、に対して、に対してを満たすが、一般には知られていない。^[7] $J(n,k)$ $\theta (J(n,1))=1$ $n>1$ $\theta (J(n,2))=n-2$ $n>2$ $\theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor$ $n>5$
の彩色数は最大^{[8]である。} $J(n,k)$ $n,\chi (J(n,k))\leq n.$
各ジョンソングラフは局所的にグリッドであり、任意の頂点の近傍の誘導部分グラフはルークグラフであることを意味する。より正確には、ジョンソングラフにおいて、各近傍はルークグラフである。^[9] $J(n,k)$ $k\times (n-k)$

自己同型群

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

交差点配列

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

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

どこ：

{\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}

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

固有値と固有ベクトル

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

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

ここで^[10]

A_{n,k}(j)=(k-j)(n-k-j)-j.

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

ジョンソン計画

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

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

未解決の問題

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

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

参照

グラスマングラフ

参考文献

^ abc Holton, DA; Sheehan, J. (1993)、「ジョンソングラフと偶数グラフ」、ピーターセングラフ、オーストラリア数学協会講演シリーズ、第7巻、ケンブリッジ：ケンブリッジ大学出版局、p. 300、doi :10.1017/CBO9780511662058、ISBN 0-521-43594-3、MR 1232658。
^ Stanić、Zoran (2017)、通常のグラフ: スペクトルアプローチ、de Gruyter、p. 63–64、ISBN 978-3-11-035135-4
^ アルスパッハ、ブライアン(2013)、「ジョンソングラフはハミルトン連結である」、Ars Mathematica Contemporanea、6 (1): 21– 23、doi : 10.26493/1855-3974.291.574。
^ Newman, Ilan; Rabinovich, Yuri (2015),単体複体のファセットグラフの連結性について, arXiv : 1502.02232 , Bibcode :2015arXiv150202232N。
^ Rispoli, Fred J. (2008),超単純体のグラフ, arXiv : 0811.2981 , Bibcode :2008arXiv0811.2981R。
^ ラムラス、マーク、ドノヴァン、エリザベス (2011)、「ジョンソングラフの自己同型群」、SIAM Journal on Discrete Mathematics、25 (1): 267– 270、doi :10.1137/090765596
^ Jørgensen, Søren F. (2025)、「ジョンソングラフのクリーク被覆数について」、Designs, Codes and Cryptography、93 (9): 3689– 3705、arXiv : 2502.15019、doi :10.1007/s10623-025-01663-3
^ "Johnson", www.win.tue.nl 、 2017年7月26日閲覧
^ Cohen, Arjeh M. (1990)、「グラフ、建物、および関連幾何学の局所認識」(PDF)、Kantor, William M.、Liebler, Robert A.、Payne, Stanley E.、Shult, Ernest E. (編)、『有限幾何学、建物、および関連トピックス：1988年7月17～23日にコロラド州ピングリーパークで開催された建物および関連幾何学に関する会議の論文』、Oxford Science Publications、オックスフォード大学出版局、pp. 85～ 94、MR 1072157特に89～90ページを参照
^ ab Brouwer、Andries E. (1989)、Distance- Regular Graphs、Cohen、Arjeh M.、Neumaier、Arnold.、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、ISBN 9783642743436、OCLC 851840609
^ Filmus, Yuval (2014)、「ブール超立方体スライス上の関数の直交基底」、The Electronic Journal of Combinatorics、23 P1.23、arXiv : 1406.0142、Bibcode :2014arXiv1406.0142F、doi :10.37236/4567、S2CID 7416206 。
^ ab キャメロン、ピーター J. (1999)、「順列群」、ロンドン数学会学生テキスト、第45巻、ケンブリッジ大学出版局、p. 95、ISBN 9780521653787。
^ このようにグラフと連想スキームを明示的に識別する方法は、Bose, RC (1963)「Strongly regular graphs, partial geometries and partial balanced designs」、Pacific Journal of Mathematics、13 (2): 389– 419、doi : 10.2140/pjm.1963.13.389、MR 0157909に示されています。。
^ Christofides, Demetres; Ellis, David; Keevash, Peter (2013)、「$r$-集合の近似頂点等周不等式」、The Electronic Journal of Combinatorics、4 (20)。
^ Godsil, CD; Meagher, Karen (2016), Erdős-Ko-Rado theorems : algebraic approach , Cambridge, United Kingdom, ISBN 9781107128446、OCLC 935456305{{citation}}: CS1 maint: location missing publisher (link)

外部リンク

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

[hs93-1] Holton, DA; Sheehan, J. (1993)、「ジョンソングラフと偶数グラフ」、ピーターセングラフ、オーストラリア数学協会講演シリーズ、第7巻、ケンブリッジ：ケンブリッジ大学出版局、p. 300、doi :10.1017/CBO9780511662058、ISBN 0-521-43594-3、MR 1232658。

[2] Stanić、Zoran (2017)、通常のグラフ: スペクトルアプローチ、de Gruyter、p. 63–64、ISBN 978-3-11-035135-4

[3] アルスパッハ、ブライアン(2013)、「ジョンソングラフはハミルトン連結である」、Ars Mathematica Contemporanea、6 (1): 21– 23、doi : 10.26493/1855-3974.291.574。

[4] Newman, Ilan; Rabinovich, Yuri (2015),単体複体のファセットグラフの連結性について, arXiv : 1502.02232 , Bibcode :2015arXiv150202232N。

[5] Rispoli, Fred J. (2008),超単純体のグラフ, arXiv : 0811.2981 , Bibcode :2008arXiv0811.2981R。

[6] ラムラス、マーク、ドノヴァン、エリザベス (2011)、「ジョンソングラフの自己同型群」、SIAM Journal on Discrete Mathematics、25 (1): 267– 270、doi :10.1137/090765596

[7] Jørgensen, Søren F. (2025)、「ジョンソングラフのクリーク被覆数について」、Designs, Codes and Cryptography、93 (9): 3689– 3705、arXiv : 2502.15019、doi :10.1007/s10623-025-01663-3

[8] "Johnson", www.win.tue.nl 、 2017年7月26日閲覧

[9] Cohen, Arjeh M. (1990)、「グラフ、建物、および関連幾何学の局所認識」(PDF)、Kantor, William M.、Liebler, Robert A.、Payne, Stanley E.、Shult, Ernest E. (編)、『有限幾何学、建物、および関連トピックス：1988年7月17～23日にコロラド州ピングリーパークで開催された建物および関連幾何学に関する会議の論文』、Oxford Science Publications、オックスフォード大学出版局、pp. 85～ 94、MR 1072157特に89～90ページを参照

[:0-10] Brouwer、Andries E. (1989)、Distance- Regular Graphs、Cohen、Arjeh M.、Neumaier、Arnold.、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、ISBN 9783642743436、OCLC 851840609

[11] Filmus, Yuval (2014)、「ブール超立方体スライス上の関数の直交基底」、The Electronic Journal of Combinatorics、23 P1.23、arXiv : 1406.0142、Bibcode :2014arXiv1406.0142F、doi :10.37236/4567、S2CID 7416206 。

[c99-12] キャメロン、ピーター J. (1999)、「順列群」、ロンドン数学会学生テキスト、第45巻、ケンブリッジ大学出版局、p. 95、ISBN 9780521653787。

[13] このようにグラフと連想スキームを明示的に識別する方法は、Bose, RC (1963)「Strongly regular graphs, partial geometries and partial balanced designs」、Pacific Journal of Mathematics、13 (2): 389– 419、doi : 10.2140/pjm.1963.13.389、MR 0157909に示されています。。

[14] Christofides, Demetres; Ellis, David; Keevash, Peter (2013)、「$r$-集合の近似頂点等周不等式」、The Electronic Journal of Combinatorics、4 (20)。

[15] Godsil, CD; Meagher, Karen (2016), Erdős-Ko-Rado theorems : algebraic approach , Cambridge, United Kingdom, ISBN 9781107128446、OCLC 935456305{{citation}}: CS1 maint: location missing publisher (link)