Hoffman%E2%80%93Singleton_graph
グラフ理論の数学分野では、ホフマン-シングルトングラフは、50個の頂点と175個のエッジを持つ7つの通常の無向グラフです。これは、パラメーター（50，7，0，1）を持つ固有の強正則グラフです。これは、すべてのムーアグラフを分類しようとしているときに、アランホフマンとロバートシングルトンによって作成されたもので、存在することが知られている最高次のムーアグラフです。各頂点の次数が7で、周囲が5のムーアグラフであるため、（7，5）-ケージです。
ホフマン-シングルトングラフ
にちなんで名付けられた
アラン・J・ホフマンロバート・R・シングルトン
頂点 50 エッジ 175 半径 2 直径 2 胴回り 5 自己同型
252，000 （PSU（3，5 2）：2）
色数 4 クロマチックインデックス 属 9
プロパティ
強正則対称ハミルトニアン積分ケージムーアグラフ
グラフとパラメータの表
ホフマン-シングルトングラフ。青いエッジのサブグラフは、10個のばらばらの五角形の合計です。
コンテンツ
1 工事
1.1 五角形と五芒星からの構築 1.2 PGからの構築（3，2）
2 代数的性質
3 サブグラフとスーパーグラフ
4 も参照してください
5 ノート
6 参考文献
工事
これがホフマン-シングルトングラフの2つの構成です。
五角形と五芒星からの構築
5つの五角形Ph と5つの五芒星Qi を取ります。Phの頂点jをQiの頂点h・i + jに結合します。（すべてのインデックスは5を法とします。）
PGからの構築（3，2）
{ abc、ade、afg、bef、bdg、cdf、ceg }などの7つの要素でファノ平面を取得し、7セットのabcdefgに2520のすべての順列を適用します。そのような各ファノ平面を正規化し（たとえば、辞書式順序に減らすことによって）、重複を破棄します。正確に15個のファノ平面が残っています。セットabcdefgの各3セット（トリプレット）は、正確に3つのファノ平面に存在します。35個のトリプレットと15個のファノ平面の間の入射は、15個の点と35個の線を持つPG（3，2）を誘導します。ホフマン-シングルトングラフを作成するには、15個のファノ平面と35個のトリプレットのそれぞれに対してグラフ頂点を作成します。各ファノ平面をレヴィグラフのように7つのトリプレットに接続し、また、奇数グラフO（4）のように互いに素なトリプレットを相互に接続します。
PG（3，2）からの非常に類似した構成を使用して、サブグラフとしてホフマン-シングルトングラフを持つヒグマン-シムズグラフを作成します。
代数的性質
ホフマン-シングルトングラフの自己同形群は、PΣU（3，5 2）と同形の位数252，000の群であり、射影特殊ユニタリ群PSU（3，5 2）と位数2の巡回群の半直積です。フロベニウス自己同形。これは、グラフの頂点、エッジ、および円弧に一時的に作用します。したがって、ホフマン-シングルトングラフは対称グラフです。グラフの頂点のスタビライザーは、 7文字の対称群S7と同型です。エッジのセットワイズスタビライザーは、Aut（A 6）= A 6 .2 2と同型です。ここで、A6は6文字の交代群です。2種類のスタビライザーは両方とも、ホフマン-シングルトングラフの自己同形群全体の最大部分群です。
ホフマン-シングルトングラフの特性多項式は次のようになります。（（ X− 7 ）。 （（ X− 2
）。 28 （（ X+ 3
）。 21 {（x-7）（x-2）^ {28}（x + 3）^ {21}}
。したがって、ホフマン-シングルトングラフは整数グラフです。そのスペクトルは完全に整数で構成されます。
ホフマン-シングルトングラフには、それぞれサイズ15の独立したセットが100個各独立集合は、他の7つの独立集合とは互いに素です。互いに素な独立集合を接続する100頂点のグラフは、2つの50頂点のサブグラフに分割できます。各サブグラフは、自己複製+乗算動作の異常なケースで、ホフマン-シングルトングラフと同形です。
サブグラフとスーパーグラフ
ホフマン-シングルトングラフには、12605サイクルと52506サイクルがピーターセングラフのコピーは525個あり、各6サイクルはそれぞれ1つのピーターセンに属します。Petersenを1つ削除すると、一意の（6，5）ケージのコピーが残ります。
ホフマン-シングルトングラフには、メビウス-カントールグラフとヒーウッドグラフのコピーも多数含まれています。これらはすべて2分割であり、+ 1と-1の交互の値で色付けすることにより、グラフの固有ベクトルを見つけることができます。固有値-3。（これは、ホフマン-シングルトングラフの唯一の負の固有値です。）まとめると、これらの固有ベクトルは、ホフマン-シングルトングラフの-3固有空間にまたがりますが、非常に完全な基礎を形成します。さらに多くのメビウス-カントールグラフまたはヒーウッドグラフが -3つの固有ベクトルがあるより。ヒーウッドグラフのコピーは750個あり、ヒーウッドグラフには位数336の自己同形群が次に、750 * 336 = 252000、ホフマン-シングルトングラフの自己同形群のサイズです。これは、ホフマン-シングルトングラフを意味します。内部のヒーウッドグラフを修正することで修正されます。同様に、自己同形群の次数が96であるメビウス-カントールグラフの2625コピーがあり、2625 * 96 = 252000であるため、類似のステートメントが成り立ちます。
ヒーウッドグラフは特にファノ平面の入射グラフであるため、上記のホフマン-シングルトングラフの15 + 35の構築に続いて、これはヒーウッドグラフが発生しなければならない多くの場所をすぐに示します。ホフマンシングルトングラフでサイズ15の独立集合を取ります。これらは100個最初の頂点と共通の8つの頂点を持つ別の独立集合を見つけます。15のそのような隣接する独立集合が8つの一般的な頂点を破棄します。残っている14個の頂点がヒーウッドグラフを形成します。したがって、以前に確立されたように、100 * 15/2=750のヒーウッドグラフが
ホフマンシングルトングラフには、奇グラフO（4）、コクセターグラフ、およびトゥッテ-コクセターグラフもサブグラフとして含まれています。
ホフマン-シングルトングラフの任意のエッジを取り、それらの2つの頂点と、それらのいずれかに直接接続されている12の頂点を破棄します。残っているグラフは、36個の頂点のシルベスターグラフです。このような各エッジは個別のシルベスターグラフにマッピングできるため、ホフマンシングルトングラフにはシルベスターグラフのコピーが175個
ホフマンシングルトングラフは、ヒグマン-シムスグラフに含まれているため、スーパーグラフになります。
も参照してください
McKay–Miller–Širáňグラフ、ホフマン–シングルトングラフを含むグラフのクラス
与えられた直径と最大次数の最大の既知のグラフの表
ノート
^ ワイスタイン、エリックW. 「ホフマン-シングルトングラフ」。MathWorld。
^ Hafner、PR「ホフマン-シングルトングラフとその自己同型」。J.代数コンビン。18、7〜12、2003。
^ Royle、G.「Re：ホフマン-シングルトンのエッジクロマチック数はいくつですか？」[email protected]の投稿。2004年9月28日。
^ Conder、MDE; ストークス、K .:「ホフマン-シングルトングラフの最小属埋め込み」、プレプリント、2014年8月。
^ Brouwer、Andries E.、 Hoffman-シングルトングラフ 。
^ ホフマン、アランJ .; シングルトン、ロバートR.（1960）、「直径2および3のムーアグラフ」（PDF）、IBM Journal of Research and Development、5（4）：497–504、doi：10.1147 / rd.45.0497、MR 0140437
。
^ Baez、John（2016年2月1日）、「Hoffman–Singleton Graph」、Visual Insight、American Mathematical Society
^ ウォン、パクケン。「ガース5と原子価6の最小グラフの一意性について」。グラフ理論ジャーナル。3：407–409。土井：10.1002/jgt.3190030413。
参考文献
コネチカット州ベンソン; Losey、NE（1971）、「ホフマンとシングルトンのグラフについて」、Journal of Combinatorial Theory、シリーズB、11（1）：67–79、doi：10.1016 / 0095-8956（71）90015-3、ISSN 0095 -8956、MR 0281658
ホルトン、DA; Sheehan、J.（1993）、ピーターセングラフ、ケンブリッジ大学出版局、pp。186および190、ISBN 0-521-43594-3。”