ホフマン・シングルトングラフ

ホフマン・シングルトングラフ
名前の由来	アラン・J・ホフマンロバート・R・シングルトン
頂点	50
エッジ	175
半径	2
直径	2 [ 1 ]
胴回り	5 [ 1 ]
自己同型	252,000 ( PSU (3,5 ^2 ):2) [ 2 ]
彩色数	4
色指数	7 [ 3 ]
属	29 [ 4 ]
プロパティ	強正則対称ハミルトニアン積分ケージムーアグラフ
グラフとパラメータの表

ホフマン・シングルトングラフ。青い辺の部分グラフは、互いに素な10個の五角形の和である。

数学のグラフ理論分野において、ホフマン・シングルトングラフは、 50頂点175辺を持つ7正則無向グラフである。パラメータ(50,7,0,1)を持つ唯一の強正則グラフである。 ^{[ 5 ]}アラン・ホフマンとロバート・シングルトンがムーアグラフの分類を試みている際に構築したグラフであり、現在知られているムーアグラフの中では最高次のグラフである。^{[ 6 ]}各頂点の次数が7で内周が5のムーアグラフであるため、 (7,5)ケージである。

工事

以下はホフマン・シングルトングラフのいくつかの構成である。^{[ 7 ]}

五角形と五芒星からの構築

5つの五角形P _hと5つの五芒星Q _iを取ります。P _hの頂点jとQ _iの頂点h · i + jを結びます（すべての添え字は5を法とします）。 ^{[ 7 ]}

PG(3,2)からの構築

7 つの要素 ({ abc, ade, afg, bef, bdg, cdf, ceg }) 上のファノ平面を取り、 7 集合abcdefgに2520 通りの偶数順列すべてを適用します。各ファノ平面を正規化 (たとえば、辞書式順序に縮小) し、重複を削除します。残るファノ平面はちょうど 15 個です。集合abcdefgの各3 集合(トリプレット)は、ちょうど 3 つのファノ平面に存在します。35 個のトリプレットと 15 個のファノ平面の接続により、15 個の点と 35 本の直線を持つPG(3,2)が生成されます。ホフマン-シングルトン グラフを作成するには、15 個のファノ平面と 35 個のトリプレットのそれぞれにグラフ頂点を作成します。各ファノ平面を、レヴィグラフのように7つのトリプレットに接続し、奇数グラフO(4) のように、互いに素なトリプレットも接続します。

PG(3,2)と非常によく似た構成は、ホフマン・シングルトングラフをサブグラフとして持つ ヒグマン・シムズグラフの構築に使用されます。

群体/マグマ上の構築

集合 とする。上の二項演算を定義し、およびにおける各に対して となるようにする。 すると、ホフマン・シングルトングラフには頂点が 個存在し、がある に対しては常にとの間に辺が存在する。 ^{[ 8 ]}（著者らは「類群」という用語を使用しているが、これは二項関数またはマグマの意味で使用されており、圏論的な意味では使用されていない。また、論文の式には誤植があることにも注意が必要である。論文では最後の項に と記述されているが、これではホフマン・シングルトングラフは生成されない。正しくはここに記述されている通りである。^{[ 9 ]}） ${\displaystyle G}$ ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{5}\times \mathbb {Z} _{5}}$ ${\displaystyle \circ}$ ${\displaystyle G}$ ${\displaystyle (a,b,c)}$ ${\displaystyle (x,y,z)}$ ${\displaystyle G}$ ${\displaystyle (a,b,c)\circ (x,y,z)=(a+x,b-bx+y,c+(-1)^{a}by+2^{a}z)}$ ${\displaystyle g\in G}$ ${\displaystyle g\in G}$ ${\displaystyle g'\in G}$ ${\displaystyle g'=g\circ s}$ ${\displaystyle s\in \{(0,0,1),(0,0,4),(1,0,0),(1,1,0),(1,2,0),(1,3,0),(1,4,0​​)\}}$ ${\displaystyle (-1)^{x}by}$ ${\displaystyle (-1)^{a}by}$

代数的性質

ホフマン・シングルトングラフの自己同型群は、射影特殊ユニタリ群PSU( 3,5 ^{2 )と}フロベニウス自己同型によって生成される位数2の巡回群との半直積であるPΣU(3,5 ² )に同型な位数252,000の群である。これはグラフの頂点、辺、弧に対して推移的に作用する。したがって、ホフマン・シングルトングラフは対称グラフである。50個の記号上の置換群として、以下の2つの置換を再帰的に適用することで生成できる^{[ 10 ]。}

${\displaystyle (1\ 44\ 22\ 49\ 17\ 43\ 9\ 46\ 40\ 45)(2\ 23\ 24\ 14\ 18\ 10\ 12\ 42\ 38\ 6)(3\ 41\ 19\ 4\ 15\ 20\ 7\ 13\ 37\ 8)(5\ 28\ 21\ 29\ 16\ 25\ 11\ 26\ 39\ 30)(27\ 47)(31\ 36\ 34\ 32\ 35)(33\ 50)}$

そして

${\displaystyle (1\ 7\ 48\ 47\ 41\ 46\ 17)(2\ 39\ 11\ 4\ 15\ 14\ 42)(3\ 32\ 28\ 9\ 23\ 6\ 43)(5\ 22\ 38\ 18\ 44\ 36\ 29)(8\ 37\ 40\ 34\ 26\ 49\ 24)(10\ 16\ 31\ 27\ 13\ 21\ 45)(19\ 33\ 25\ 35\ 50\ 30\ 20)}$

グラフの頂点の安定集合は、7文字の対称群S ₇と同型である。辺の集合的安定集合は、Aut(A ₆ ) = A ₆ .2 ²と同型である。ここで、A _{6は6文字の}交代群である。2種類の安定集合はどちらも、ホフマン・シングルトングラフの自己同型群全体の最大部分群である。

ホフマン・シングルトングラフの特性多項式は に等しい。したがって、ホフマン・シングルトングラフは整数グラフであり、そのスペクトルはすべて整数で構成される。 ${\displaystyle (x-7)(x-2)^{28}(x+3)^{21}}$

ホフマン・シングルトングラフには、それぞれサイズが15の独立集合がちょうど100個存在します。各独立集合は、他の独立集合とちょうど7つ互いに素です。素の独立集合同士を結ぶ100頂点グラフは、それぞれがホフマン・シングルトングラフと同型である2つの50頂点サブグラフに分割でき、これは自己複製と増殖という珍しい動作を呈します。

サブグラフとスーパーグラフ

ホフマン・シングルトングラフには、5-閉路が1260個、6-閉路が5250個あります。ピーターセングラフは525個あり、それぞれの6-閉路はそれぞれ1つのピーターセングラフに属します。ピーターセングラフを1つ取り除くと、唯一の(6,5)-ケージのコピーが残ります。ホフマン・シングルトングラフには、奇数グラフO(4)、コクセターグラフ、およびタット・コクセターグラフも部分グラフとして含まれています。^{[ 5 ]}

ホフマン・シングルトングラフの任意の辺から、その2つの頂点と、どちらかに直接接続している12個の頂点を削除します。残ったグラフは36頂点のシルベスターグラフです。これらの辺はそれぞれ異なるシルベスターグラフにマッピングできるため、ホフマン・シングルトングラフにはシルベスターグラフのコピーが175個存在します。^{[ 5 ]}

ホフマンシングルトングラフはヒグマン・シムズグラフに含まれているため、スーパーグラフとなる。^{[ 5 ]}

参照

• マッケイ・ミラー・シラングラフ（ホフマン・シングルトングラフを含むグラフのクラス）
• 与えられた直径と最大次数を持つ既知の最大グラフの表

注記

1. Weisstein, Eric W. 「Hoffman-Singleton Graph」 . MathWorld .
2. Hafner, PR「ホフマン-シングルトングラフとその自己同型性」J. Algebraic Combin. 18, 7–12, 2003.
3. Royle, G. 「Re: ホフマン・シングルトンのエッジ彩色数は？」[e-mail] 投稿。2004年9月28日。 [1]
4. Conder, MDE; Stokes, K.:「Hoffman-Singletonグラフの最小属数埋め込み」、プレプリント、2014年8月。
5. Brouwer、Andries E.、ホフマン-シングルトンのグラフ。
6. ホフマン、アラン・J.; シングルトン、ロバート・R. (1960)、「直径2および3のムーアグラフ」(PDF)、IBM Journal of Research and Development、5 (4): 497– 504、doi : 10.1147/rd.45.0497、MR 0140437 。
7. Baez, John (2016年2月1日)、「Hoffman–Singleton Graph」、Visual Insight、アメリカ数学会
8. Chishwashwa, N.; Faber, V.; Streib, N. (2022). 「有向グラフネットワークと群状体」. arXiv : 2208.10537 [ math.CO ].
9. ハーダー、ジャニス（2024年1月24日）、マストドンのメッセージ
10. これらのジェネレータはGAPによって公開されています。もちろん、このグループには他にも多くのジェネレータがあります。

参考文献

• ベンソン, CT; ロジー, NE (1971)、「ホフマンとシングルトンのグラフについて」、Journal of Combinatorial Theory, Series B , 11 (1): 67– 79, doi : 10.1016/0095-8956(71)90015-3 , ISSN  0095-8956 , MR  0281658
• Chishwashwa, N.; Faber, V.; Streib, N. (2022)「有向グラフネットワークと群体」、arXiv : 2208.10537 [ math.CO ]
• ホルトン, DA; シーハン, J. (1993), 『ピーターセングラフ』 ,ケンブリッジ大学出版局, pp. 186 and 190, ISBN 0-521-43594-3。