ケイリーグラフ
数学の世界では、群の持つ複雑な構造をより直感的に理解するために、グラフを用いる方法があります。その代表的なものが、アーサー・ケイリーにその名を由来するケイリーグラフです。これは、特定の生成集合を持つ群に対して構成されるグラフであり、特に組合せ論や幾何学的群論において中心的な道具として活用されています。
ケイリーグラフΓは、与えられた群Gとその生成集合Sに基づいて構築される有向グラフです。まず、群Gのそれぞれの元に対応する頂点をグラフに割り当てます。したがって、グラフの頂点集合V(Γ)は、群Gの元そのものと同一視できます。次に、生成集合Sの各元sに対して、固有の色csを割り当てます。そして、群Gの任意の元gと生成集合Sの任意の元sについて、元gに対応する頂点から元gsに対応する頂点へ、色csを持つ有向辺を引きます。つまり、辺集合E(Γ)は、(g, gs)の形をした順序対から構成され、その辺の色はsによって決まります。
幾何学的群論などの文脈では、通常、生成集合Sは有限であり、かつ対称的である（すなわち、Sに含まれる元の逆元もSに含まれる：S = S⁻¹）と仮定され、さらに単位元は含まれないとされます。この場合、辺の色や向きを考慮しないグラフは、自己ループを含まない単純な無向グラフとなります。
ケイリーグラフの形状は、群の種類と生成集合の選び方によって大きく異なります。
無限巡回群Zを考え、生成集合として{+1, -1}を選ぶと、ケイリーグラフは無限に続く直線状のパスとなります。
同様に、位数nの有限巡回群Znに対し、生成集合を{+1, -1}とすると、ケイリーグラフはn個の頂点を持つ閉路Cnになります。これはサーキュラントグラフの一種です。
直積群のケイリーグラフは、個々の群に対応するケイリーグラフの直積として得られます。例えば、整数環の直積群Z²のケイリーグラフは平面上の無限格子となり、有限巡回群の直積Zn × Zmのケイリーグラフはトーラス上の有限格子に対応します。
二面体群D₄の場合、生成元の選び方によってグラフの構造が変わることがあります。例えば、ある生成元の組を選ぶと有向辺と無向辺が混在するグラフになり得ますが、別の生成元の組（例えば位数が2の元のみ）を選ぶと無向グラフとなることもあります。
2つの生成元a, bから生成される自由群F₂に対し、生成集合を{a, a⁻¹, b, b⁻¹}とすると、そのケイリーグラフは閉路を一切持たない無限の木構造、いわゆるベーテ格子となります。これはバナッハ・タルスキーのパラドックスの議論にも関連します。
非可換な無限群である離散ハイゼンベルク群のケイリーグラフは、3次元空間に埋め込まれたような構造を持ち、4次元的な「体積増加」を示すといった興味深い性質を持ちます。
ケイリーグラフは、群の作用と密接に関連しています。群Gは、その元hを用いてグラフの各頂点gをhgへと移す「左からの乗算」という作用を考えられます。この作用はグラフの辺の構造を保ち、頂点集合に対して単純推移的です。つまり、どの頂点も別のどの頂点へも、群の元の作用によってちょうど1通りの方法で移すことができます。この性質はケイリーグラフを特徴づける重要な要素であり、グラフが群Gのケイリーグラフであることと、グラフがグラフ自己同型として群Gの単純推移的な作用を持つことは同値であるというサビドゥッシの定理として知られています。
ケイリーグラフの構造は、群の代数的性質を反映しています。例えば、生成集合Sがk個の元を持つ場合、対応するケイリーグラフの各頂点は、有向グラフとしては入次数k、出次数kとなります。生成集合が対称的な場合は、次数kの正則無向グラフとなります。ケイリーグラフにおける閉路の存在は、生成元間に何らかの関係式があることを示唆しています。逆に、自由群のように関係式がない群のケイリーグラフは閉路を持ちません。
また、有限ケイリーグラフを無向グラフと見なした場合、その連結性についても興味深い性質があります。例えば、頂点連結度はグラフの次数の少なくとも2/3であり、生成集合が極小であれば次数と等しくなります。
ケイリーグラフと同様の考え方で、群の部分群Hの右剰余類を頂点とするグラフを構成することもできます。これはSchreier coset グラフと呼ばれ、群論における剰余類数え上げなどの手法（例えばTodd–Coxeterアルゴリズム）の基礎となっています。
ケイリーグラフは、代数的グラフ理論を通じて群の構造を調べるための強力なツールとなります。特に無限群の研究では、ケイリーグラフ上の距離（語距離と呼ばれます）や、生成集合の選び方に依らないグラフの「粗い」幾何学的性質が、群そのものの不変量として幾何学的群論の根幹をなしています。
歴史的には、ケイリーグラフは1878年にケイリーによって有限群のために導入されましたが、20世紀初頭にマックス・デーンによって「Gruppenbild（群図）」として再導入され、幾何学的群論の発展に大きく貢献しました。特に、デーンは曲面の基本群に関する研究にケイリーグラフを応用し、その重要性を示しました。
このように、ケイリーグラフは、群の抽象的な代数構造とグラフの具体的な組合せ的・幾何学的構造を結びつけ、様々な角度から群を研究するための不可欠な概念となっています。
定義と構成
ケイリーグラフΓは、与えられた群Gとその生成集合Sに基づいて構築される有向グラフです。まず、群Gのそれぞれの元に対応する頂点をグラフに割り当てます。したがって、グラフの頂点集合V(Γ)は、群Gの元そのものと同一視できます。次に、生成集合Sの各元sに対して、固有の色csを割り当てます。そして、群Gの任意の元gと生成集合Sの任意の元sについて、元gに対応する頂点から元gsに対応する頂点へ、色csを持つ有向辺を引きます。つまり、辺集合E(Γ)は、(g, gs)の形をした順序対から構成され、その辺の色はsによって決まります。
幾何学的群論などの文脈では、通常、生成集合Sは有限であり、かつ対称的である（すなわち、Sに含まれる元の逆元もSに含まれる：S = S⁻¹）と仮定され、さらに単位元は含まれないとされます。この場合、辺の色や向きを考慮しないグラフは、自己ループを含まない単純な無向グラフとなります。
多様な例
ケイリーグラフの形状は、群の種類と生成集合の選び方によって大きく異なります。
無限巡回群Zを考え、生成集合として{+1, -1}を選ぶと、ケイリーグラフは無限に続く直線状のパスとなります。
同様に、位数nの有限巡回群Znに対し、生成集合を{+1, -1}とすると、ケイリーグラフはn個の頂点を持つ閉路Cnになります。これはサーキュラントグラフの一種です。
直積群のケイリーグラフは、個々の群に対応するケイリーグラフの直積として得られます。例えば、整数環の直積群Z²のケイリーグラフは平面上の無限格子となり、有限巡回群の直積Zn × Zmのケイリーグラフはトーラス上の有限格子に対応します。
二面体群D₄の場合、生成元の選び方によってグラフの構造が変わることがあります。例えば、ある生成元の組を選ぶと有向辺と無向辺が混在するグラフになり得ますが、別の生成元の組（例えば位数が2の元のみ）を選ぶと無向グラフとなることもあります。
2つの生成元a, bから生成される自由群F₂に対し、生成集合を{a, a⁻¹, b, b⁻¹}とすると、そのケイリーグラフは閉路を一切持たない無限の木構造、いわゆるベーテ格子となります。これはバナッハ・タルスキーのパラドックスの議論にも関連します。
非可換な無限群である離散ハイゼンベルク群のケイリーグラフは、3次元空間に埋め込まれたような構造を持ち、4次元的な「体積増加」を示すといった興味深い性質を持ちます。
特徴づけと性質
ケイリーグラフは、群の作用と密接に関連しています。群Gは、その元hを用いてグラフの各頂点gをhgへと移す「左からの乗算」という作用を考えられます。この作用はグラフの辺の構造を保ち、頂点集合に対して単純推移的です。つまり、どの頂点も別のどの頂点へも、群の元の作用によってちょうど1通りの方法で移すことができます。この性質はケイリーグラフを特徴づける重要な要素であり、グラフが群Gのケイリーグラフであることと、グラフがグラフ自己同型として群Gの単純推移的な作用を持つことは同値であるというサビドゥッシの定理として知られています。
ケイリーグラフの構造は、群の代数的性質を反映しています。例えば、生成集合Sがk個の元を持つ場合、対応するケイリーグラフの各頂点は、有向グラフとしては入次数k、出次数kとなります。生成集合が対称的な場合は、次数kの正則無向グラフとなります。ケイリーグラフにおける閉路の存在は、生成元間に何らかの関係式があることを示唆しています。逆に、自由群のように関係式がない群のケイリーグラフは閉路を持ちません。
また、有限ケイリーグラフを無向グラフと見なした場合、その連結性についても興味深い性質があります。例えば、頂点連結度はグラフの次数の少なくとも2/3であり、生成集合が極小であれば次数と等しくなります。
関連概念と応用
ケイリーグラフと同様の考え方で、群の部分群Hの右剰余類を頂点とするグラフを構成することもできます。これはSchreier coset グラフと呼ばれ、群論における剰余類数え上げなどの手法（例えばTodd–Coxeterアルゴリズム）の基礎となっています。
ケイリーグラフは、代数的グラフ理論を通じて群の構造を調べるための強力なツールとなります。特に無限群の研究では、ケイリーグラフ上の距離（語距離と呼ばれます）や、生成集合の選び方に依らないグラフの「粗い」幾何学的性質が、群そのものの不変量として幾何学的群論の根幹をなしています。
歴史的には、ケイリーグラフは1878年にケイリーによって有限群のために導入されましたが、20世紀初頭にマックス・デーンによって「Gruppenbild（群図）」として再導入され、幾何学的群論の発展に大きく貢献しました。特に、デーンは曲面の基本群に関する研究にケイリーグラフを応用し、その重要性を示しました。
このように、ケイリーグラフは、群の抽象的な代数構造とグラフの具体的な組合せ的・幾何学的構造を結びつけ、様々な角度から群を研究するための不可欠な概念となっています。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。