| ヒグマン・シムズグラフ | |
|---|---|
 ポール・R・ハフナーの構想に基づく図面。[1] | |
| 名前の由来 | ドナルド・G・ヒグマン チャールズ・C・シムズ |
| 頂点 | 100 |
| エッジ | 1100 |
| 半径 | 2 |
| 直径 | 2 |
| 胴回り | 4 |
| 自己同型 | 88,704,000 ( HS :2) |
| プロパティ | 強正則 エッジ推移 ハミルトン オイラー |
| グラフとパラメータの表 | |
数学のグラフ理論において、ヒグマン・シムズグラフは、 100個の頂点と1100個の辺を持つ22正則 無向グラフである。これは、隣接する頂点のペアが共通の隣接頂点を共有せず、隣接する頂点のペアがそれぞれ6つの共通隣接頂点を共有する、唯一の強正則グラフsrg(100,22,0,6)である。 [2]メスナー (1956) [3]によって最初に構築され、1968年にドナルド・G・ヒグマンとチャールズ・C・シムズによって、ホフマン・シングルトングラフの自己同型群における指数2の部分群であるヒグマン・シムズ群を定義する方法として再発見された。[4]
工事
M22グラフより
強く正則なグラフsrg(77,16,0,4) であるM22 グラフに、S(3,6,22) の点に対応する 22 個の新しい頂点を追加します。各ブロックはその点に接続され、1 つの追加頂点C が22 個の点に接続されます。
ホフマン・シングルトングラフから
ホフマン・シングルトングラフには、サイズ15の独立集合が100個あります。100個の対応する頂点を持つ新しいグラフを作成し、対応する独立集合にちょうど0個または8個の要素が共通する頂点同士を接続します。結果として得られるホフマン・シングルトングラフは、 352通りの方法でホフマン・シングルトングラフの2つのコピーに分割できます。
立方体から
頂点に 000、001、010、...、111 とラベル付けされた立方体を取ります。頂点の 4 セットが可能な 70 種類すべてを取り、XORが 000 になる頂点のみを残します。このような 4 セットは 14 種類あり、6 つの面 + 6 つの対角長方形 + 2 つのパリティ四面体に対応します。これは、8 つの点に対する 3-(8,4,1)ブロック設計で、ブロック サイズが 4 のブロックが 14 個あり、各点は 7 つのブロックに出現し、各点のペアは 3 回出現し、各 3 つの点の組み合わせは 1 回だけ出現します。元の 8 つの頂点を 8! = 40320 通りのいずれかに並べ替え、重複を破棄します。頂点のラベルを再度付ける方法は 30 通りあります (つまり、点の並べ替えによって互いに同型になる 30 通りの設計)。これは、自己同型が1344 個あり、40320/1344 = 30 となるためです。
30 個のデザインそれぞれに頂点を作成し、各デザインの各行に頂点を作成します (このような行は合計 70 個あり、各行は 8 個が 4 セットで、6 つのデザインに出現します)。各デザインをその 14 行に接続します。互いに素なデザインを互いに接続します (各デザインは他の 8 つのデザインと素です)。行が共通の要素を 1 つだけ持つ場合は、行を互いに接続します (このような隣接行は 4x4 = 16 個あります)。結果として得られるグラフは Higman–Sims グラフです。行は他の 16 行と 6 つのデザインに接続され、次数 22 です。デザインは 14 行に接続され、8 つの素なデザインに接続され、次数 22 です。したがって、100 個の頂点はすべて次数 22 になります。
代数的性質
ヒグマン・シムズグラフの自己同型群は、位数 44,352,000 のヒグマン・シムズ群と位数 2 の巡回群との半直積に同型な位数 88,704,000 の群である。[ 5 ]この群は任意の辺を他の任意の辺につなぐ自己同型を持ち、ヒグマン・シムズグラフを辺推移グラフにする。 [ 6]外側の要素はグラフ上で奇数の順列を誘導する。前述のように、ヒグマン・シムズグラフを一対のホフマン・シングルトングラフに分割する方法は 352 通りある。これらの分割は実際にはそれぞれサイズが 176 の 2 つの軌道に分かれており、ヒグマン・シムズ群の外側の要素はこれらの軌道を交換している。[7]
ヒグマン・シムズグラフの特性多項式は ( x − 22)( x − 2) 77 ( x + 8) 22 である。したがって、ヒグマン・シムズグラフは整数グラフであり、そのスペクトルはすべて整数で構成される。また、この特性多項式を持つ唯一のグラフであるため、スペクトルによって決定されるグラフである。
リーチ格子内部
Higman–Sims グラフは、 Leech 格子 の内部で自然に発生します。つまり、 X、Y、Z がLeech 格子内の 3 つの点で、距離XY、XZ、YZがそれぞれ である場合、距離XT、YT、ZTがすべて 2 に等しいような Leech 格子点Tがちょうど 100 個存在し、そのような 2 つの点TとT ′ をそれらの間の距離が であるときに接続した場合、結果として得られるグラフは Higman–Sims グラフと同型になります。さらに、 X、Y、Zのそれぞれを固定する Leech 格子のすべての自己同型 (つまり、それを固定するユークリッド合同) の集合は、 Higman–Sims 群です ( XとYの交換を許可すると、すべてのグラフ自己同型の位数 2 の拡張が得られます)。これは、ヒグマン・シムズ群がコンウェイ群Co 2（その2次拡張を含む）とCo 3、そして結果的にCo 1 の内部に現れることを示している。[8]
参考文献
- ^ Hafner, PR (2004). 「Hoffman–SingletonとHigman–Simsのグラフについて」(PDF) . The Electronic Journal of Combinatorics . 11 (1) R77: R77(1–32). doi : 10.37236/1830 .。
- ^ Weisstein, Eric W.「Higman–Simsグラフ」. MathWorld .
- ^ メスナー、デール・マーシュ (1956).部分バランス型不完全ブロック実験計画と連想法の特定の組み合わせ特性の調査、ラテン方格法および関連タイプの計画の詳細な研究(博士論文). ミシガン州立大学統計学部. MR 2612633.
- ^ ヒグマン、ドナルド G.シムズ、チャールズ C. (1968)。 「オーダー44,352,000の単純なグループ」(PDF)。数学的ツァイシュリフト。105 (2): 110–113。土井:10.1007/BF01110435。hdl : 2027.42/46258。S2CID 32803979。。
- ^ Brouwer, Andries E.「Higman–Sims グラフ」。
- ^ Brouwer, AEおよびHaemers, WH「ゲヴィルツグラフ：グラフスペクトル理論の演習」Euro. J. Combin. 14, 397–407, 1993.
- ^ Conway, JH ; Curtis, RT; Norton, SP ; Parker, RA ; Wilson, RA (1985). Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups . （JG Thackrayの計算支援付き）. Oxford University Press. ISBN 978-019853199-9。
- ^ ジョン・H・コンウェイ;スローン、ニール JA (2010 年 12 月)。球のパッキング、格子、およびグループ。 Grundlehren der mathematischen Wissenschaften (第 3 版)。スプリンガー・フェルラーグ。ISBN 978-1-4419-3134-4。第10章（ジョン・H・コンウェイ、「例外群に関する三つの講義」）、§3.5（「ヒグマン・シムズ群とマクラフリン群」）、pp.292–293。
