フルクトの定理

フルヒトの定理は代数的グラフ理論における結果であり、1936年にデーネス・ケーニッヒによって予想され^[1]、1939年にロバート・フルヒトによって証明された^[2] 。これは、すべての有限群は有限無向グラフの対称群であるということを述べている。より強い主張としては、任意の有限群Gに対して、それぞれの自己同型群がGと同型であるような、同型でない単純連結グラフが無限に存在するということである。

証明の主なアイデアは、Gのケイリーグラフに、 Gの生成元を互いに区別するために辺に色と向きを追加することで、目的の自己同型群が得られることを観察することです。したがって、これらの辺のそれぞれを適切なサブグラフに置き換え、各置き換えサブグラフ自体が非対称で、2つの置き換えが同じ色の辺を置き換える場合にのみ同型になるようにすると、これらの置き換えを実行して作成された無向グラフもG を対称群として持つことになります。^[3]

3つの例外（位数3、4、5の巡回群）を除いて、すべての群は、頂点が2つの軌道しか持たないグラフの対称性として表すことができます。したがって、グラフの頂点の数は、最大で群の位数の2倍です。例外の集合が大きくなるほど、ほとんどの有限群は、頂点の数が群の位数に等しい頂点推移グラフの対称性として表すことができます。 ^[4]

フルヒトの定理には、ある制限されたグラフ族には、あらゆる対称群を実現するのに十分なグラフが含まれていることを示す、より強力なバージョンがあります。フルヒト^{[5] は}、実際に望ましい特性を持つ3 正則グラフが可算なほど多く存在することを証明しました。たとえば、12 の頂点と 18 の辺を持つ 3 正則グラフであるフルヒト グラフ には非自明な対称性がないため、自明な群に対してこのタイプの実現が提供されます。ゲルト サビドゥッシ は、すべての群は、すべての正の整数値k (正則グラフの場合は 、k彩色グラフの場合は) に対して、可算なほど多くの異なるk正則グラフ、k頂点連結グラフ、またはk彩色グラフ の対称群として実現できることを示しました。^[6]すべてのグラフは、その辺と頂点の包含半順序から再構成できること、すべての有限半順序はバーコフの表現定理により有限分配格子と同値であることから、すべての有限群は分配格子の対称性、および格子のグラフである中位グラフの対称性として実現できることがわかります。^{[3]すべての有限群を}強正則グラフの対称性の群として実現することができます。^{[7]すべての有限群は、}識別数2のグラフの対称性としても実現できます。つまり、グラフを 2 色で（不適切に）着色して、グラフの対称性のいずれも着色を保持しないようにすることができます。^[8]${\displaystyle k\geq 3}$${\displaystyle k\geq 2}$

しかし、いくつかの重要なグラフのクラスは、すべてのグループをその対称性として実現することができません。Camille Jordan は、木の対称群を、自明なグループを含み、互いの直積と対称群との花輪積で閉じている有限群の最小の集合であると特徴付けました。^[9]特に、位数 3 の巡回群は木の対称群ではありません。平面グラフも、すべてのグループをその対称性として実現することはできません。たとえば、平面グラフの対称性である有限単純群は、巡回群と交代群だけです。^[10]より一般的には、すべてのマイナー閉グラフ族は、そのグラフの対称性によってすべての有限群を表すことができません。^[11] László Babai は、より強く、各マイナー閉族は有限個の非巡回有限単純群のみを表すことができると推測しています。^[12] ${\displaystyle A_{5}}$

イズビッキは1959年にこれらの結果を拡張し、任意の有限対称群を実現する無限グラフが無数に存在することを示した。 ^[13]最後に、ヨハネス・デ・グルートとサビドゥッシは1959年と1960年に独立して、任意の群（群が有限であるという仮定を捨て、選択公理の仮定を付ける）は無限グラフの対称群として実現できることを証明した。^{[14] [15]}

• Babai、László (1995)、「自己同型群、同型、再構成」(PDF)、Graham、Ronald L. ;マーティン・グレッチェル; Lovász、László (編)、Handbook of Combinatorics、vol. II、北オランダ、1447 ～ 1540 ページ。
• de Groot、Johannes (1959)、「同相同型群で表される群」、Mathematische Annalen、138 : 80–102、doi :10.1007/BF01369667、hdl : 10338.dmlcz/101909、ISSN  0025-5831、MR  0119193。
• Robert Frucht (1939)、「Herstellung von Graphen mit vorgegebener abstrakter Gruppe.」、Compositio Mathematica (ドイツ語)、6 : 239–250、ISSN  0010-437X、Zbl  0020.07804。
• フルクト、ロバート(1949)、「与えられた抽象群による 3 次グラフ」、Canadian Journal of Mathematics、1 (4): 365–378、doi : 10.4153/CJM-1949-033-6、ISSN  0008-414X、MR  0032987、2011-07-06 にオリジナルからアーカイブ、 2010-02-20 に取得。
• Izbicki、Herbert (1959)、「Unendliche Graphen endlichen Grades mit vorgegebenen Eigenschaften」、Monatshefte für Mathematik、63 (3): 298–301、doi :10.1007/BF01295203、MR  0105372。
• Kőnig、Dénes (1936)、Theorie der endlichen und unendlichen Graphen、ライプツィヒ：Akademische Verlagsgesellschaft、p. 5Babai (1995) より引用。
• サビドゥッシ、ゲルト(1957)、「与えられた群と与えられたグラフ理論的特性を持つグラフ」、カナダ数学ジャーナル、9 : 515–525、doi :10.4153/cjm-1957-060-7、ISSN  0008-414X、MR  0094810。
• Sabidussi、Gert (1960)、「与えられた無限群を含むグラフ」、Monatshefte für Mathematik、64 : 64–67、doi :10.1007/BF01319053、MR  0115935。