ケイリーグラフ

ふたつの元 テンプレート:Mvar と テンプレート:Mvar を生成元とする自由群 テンプレート:Math のケイリーグラフ

自由積 $Z_2*Z_3=⟨a,b\mid a^2=b^3=1⟩$ のケイリーグラフ（テンプレート:Math）

数学においてケイリーグラフ（テンプレート:Lang-en-short）とは群の抽象的な構造を表現するアーサー・ケイリーの名に由来するグラフである。特定の（ふつうは有限な）群の生成集合に対して使われ、組合せ論的あるいは幾何学的群論における中心的な道具である。

定義

テンプレート:Mvar を群、テンプレート:Mvar をその生成集合とする。ケイリーグラフ テンプレート:Math とは以下のように構成されるグラフ彩色化有向グラフであるテンプレート:Efn：

• 群 テンプレート:Mvar の各元 テンプレート:Mvar に対して頂点を割り当てる：テンプレート:Math の頂点集合 テンプレート:Math を テンプレート:Mvar と同一視する。
• 生成集合 テンプレート:Mvar の各元 テンプレート:Mvar に対して色 テンプレート:Mvar を割り当てる。
• 群 テンプレート:Mvar の元 テンプレート:Mvar と生成集合 テンプレート:Mvar の元 テンプレート:Mvar に対して元 テンプレート:Mvar と テンプレート:Mvar に対応する頂点を色 テンプレート:Mvar の有向辺でむすぶ。つまり辺集合 テンプレート:Math は テンプレート:Math の形をした組からなり、色は テンプレート:Math から定まる。

幾何学的群論ではふつう集合 テンプレート:Mvar は有限かつ対称（つまり テンプレート:Math）であり、単位元を含まないと仮定する。このとき色を忘れたケイリーグラフは単純グラフである：辺に向きはなく、ループを含まない。

例

• 無限巡回群 テンプレート:Math と テンプレート:Mvar として生成元 テンプレート:Math とその逆元 テンプレート:Math からなる集合を考えるとケイリーグラフは無限の道である。
• 同様に、位数 テンプレート:Mvar の有限巡回群 テンプレート:Math と テンプレート:Mvar として生成元とその逆元からなる集合を考えるとケイリーグラフは閉路 テンプレート:Mvar である。より一般に、有限巡回群のケイリーグラフはちょうど circulant graphs に一致する。
• 直積群のケイリーグラフは対応するケイリーグラフの直積である。よって四元 テンプレート:Math を生成元とするアーベル群 テンプレート:Math のケイリーグラフは平面 テンプレート:Math 上の無限格子であり、直積 テンプレート:Math のケイリーグラフは同様の生成元をとるとトーラス上の テンプレート:Math 有限格子である。

二面体群 テンプレート:Math の元 テンプレート:Mvar と テンプレート:Mvar を生成集合とするケイリーグラフ

テンプレート:Math の対合 テンプレート:Mvar と テンプレート:Mvar を生成集合とするケイリーグラフ

• 二面体群 テンプレート:Math の生成元 テンプレート:Mvar と テンプレート:Mvar に関するケイリーグラフは左のように表される。赤い有向辺は テンプレート:Font color の合成を表す。テンプレート:Mvar は対合なので テンプレート:Font color の合成を表す青い辺は無向とした。したがってグラフはごたまぜである：8つの頂点、8つの有向辺、そして4つの無向辺。群 テンプレート:Math の乗積表は表示

$D_4=⟨a,b\mid a^4=b^2=e,ab=b{a}^3⟩$

から導くことができる。テンプレート:Math の異なるケイリーグラフは右のように表される。テンプレート:Font color は先ほどと同様に水平鏡映で、青い無向辺で表す。テンプレート:Font color は対角鏡映でピンクの無向辺で表す。どちらの鏡映も対合なので右のケイリーグラフは無向グラフである。このグラフは表示

$D_4=⟨b,c\mid b^2=c^2=e,bcbc=cbcb⟩$

に対応する。

• ふたつの元 テンプレート:Mvar と テンプレート:Mvar を生成元とする自由群 テンプレート:Math の生成集合 テンプレート:Math に対応するケイリーグラフは本記事の冒頭に掲げられている。ここで テンプレート:Mvar は単位元を表す。辺に沿った右への移動は テンプレート:Mvar の右からの乗算で表され、辺に沿った上への移動は テンプレート:Mvar の右からの乗算で表される。自由群は関係式を持たないので、ケイリーグラフは閉路を持たない。このケイリーグラフはバナッハ・タルスキーのパラドックスの証明における主要な要素である。

ハイゼンベルク群のケイリーグラフの一部（色は単なる装飾である）

• 離散ハイゼンベルク群

$\{\left(\begin{array}{ccc}1& x& z\\ 0& 1& y\\ 0& 0& 1\end{array}\right):x,y,z\in \mathbb{Z}\}$

のケイリーグラフは右のように表される。生成元は成分 テンプレート:Mvar における 1, 0, 0 の置換から与えられる三つの行列 テンプレート:Mvar である。これらの生成元は図から読み取れる関係式 テンプレート:Math, テンプレート:Math, テンプレート:Math を満たす。この群は非可換無限群で三次元空間で表すことができ、ケイリーグラフは四次元の volume growth を持つ。

特徴づけ

群 テンプレート:Mvar は自分自身に左からの乗算で作用する（ケイリーの定理を参照）。これは群 テンプレート:Mvar がそのケイリーグラフに作用しているとみることができる。明示的には、元 テンプレート:Math は頂点 テンプレート:Math を テンプレート:Math へ移す。ケイリーグラフの辺集合この作用で保たれる：辺 テンプレート:Math は辺 テンプレート:Math へ移される。群の左からの乗算による作用は単純推移的であり、とくにケイリーグラフは頂点推移的である。これは以下のケイリーグラフの特徴づけに繋がる：

Sabidussiの定理：グラフ テンプレート:Math が群 テンプレート:Mvar のケイリーグラフである必要十分条件はグラフがグラフ自己同型として群 テンプレート:Mvar の単純推移的な作用を持つことである。

ケイリーグラフ テンプレート:Math から群 テンプレート:Mvar と生成集合 テンプレート:Mvar を復元するには、まず頂点 テンプレート:Math を選び、群の単位元でラベルづける。そしてグラフ テンプレート:Math の各頂点 テンプレート:Mvar に対し、テンプレート:Math を テンプレート:Mvar へ移す群 テンプレート:Mvar のただひとつの元でラベルづける。生成集合が有限である必要十分条件はグラフが局所有限であることである。

基本的な性質

• もし生成集合の元 テンプレート:Mvar が対合ならば対応する辺は無向辺で表されることが多い。
• ケイリーグラフ テンプレート:Math は生成集合 テンプレート:Mvar の選び方に本質的に依存する。たとえば生成集合 テンプレート:Mvar が テンプレート:Mvar 個の元を持つならば、ケイリーグラフの各頂点は入次数 テンプレート:Mvar かつ出次数 テンプレート:Mvar である。生成集合 テンプレート:Mvar が対称のとき、ケイリーグラフは次数 テンプレート:Mvar の正則有向グラフである。
• ケイリーグラフの閉路は生成集合 テンプレート:Mvar の元の間に関係式があることを示している。
• もし テンプレート:Math が群の全射準同型で生成集合 テンプレート:Mvar の像 テンプレート:Math が互いに相異なるならば、グラフの被覆 テンプレート:Math を誘導する。とくに群 テンプレート:Mvar が テンプレート:Mvar 個の生成元をもち、すべての位数が テンプレート:Math と異なり、集合 テンプレート:Mvar がそれらの生成元とその逆元から成るならば、ケイリーグラフ テンプレート:Math は同じ生成元を持つ自由群に対応する次数 テンプレート:Math の無限正則木によって被覆される。
• グラフ テンプレート:Math はたとえ集合 テンプレート:Mvar が群 テンプレート:Mvar を生成していないときでさえ構成することができる。けれども、グラフは非連結となり、ケイリーグラフとして考えることはできない。このときグラフの各連結成分は テンプレート:Mvar によって生成される部分群の剰余類を表す。
• 有限ケイリーグラフを無向グラフとして考えたとき、頂点連結度は少なくともグラフの次数の テンプレート:Math はある。もし生成集合が極小ならば、頂点連結度は次数と等しい。辺連結度はどんな場合でも次数と等しいテンプレート:Sfn。
• 有限アーベル群 テンプレート:Mvar のケイリーグラフ テンプレート:Math が定める隣接行列の固有値は、既約指標 テンプレート:Mvar を用いて テンプレート:Math と表せるテンプレート:Sfn。また各固有値に属する固有ベクトルも既約指標の値を並べることで得られる。

Schreier coset グラフ

頂点としてある固定した部分群 テンプレート:Mvar の右剰余類を取れば同種の構成——Schreier coset グラフ——を考えることができる。これは剰余類数え上げやTodd–Coxeterアルゴリズムの根底にある。

群論とのつながり

群の構造に関する知識はグラフの隣接行列やとくにスペクトラルグラフ理論の定理を適用することで得ることができる。

幾何学的群論

無限群に対してケイリーグラフのcoarse幾何学は幾何学的群論の基本である。有限生成群に対して、これは有限生成集合の選び方に依らず、したがってその群に固有の性質である。これは無限群に対してのみ興味のあることである：すべての有限群は全体を有限生成集合として選ぶことができるので一点（あるいは自明な群）とcoarse同値である。

形式的には、与えられた生成元に対して、語距離（ケイリーグラフ上の自然な距離）があり、距離空間を定める。この空間のcoarse同値の代表系は群の不変量である。

歴史

ケイリーグラフは1878年にアーサー・ケイリーによって有限群に対して初めて考えられた。マックス・デーンは1909–1910年の群論に関する未刊行の講義録でGruppenbild (group diagram)という名前で再導入し、これが今日の幾何学的群論につながる。デーンの最も重要な応用は種数 テンプレート:Math の曲面の基本群に関する語の問題の解法で、これは曲面上の閉曲線が可縮かどうかを決定するという位相的な問題と等価である。

ベーテ格子

テンプレート:Main ベーテ格子あるいはケイリー木は テンプレート:Mvar 個の生成元をもつ自由群のケイリーグラフである。テンプレート:Mvar 個の生成元をもつ群 テンプレート:Mvar の表示は テンプレート:Mvar 個の生成元をもつ自由群から群 テンプレート:Mvar への全射準同型と対応し、ケイリーグラフの観点からはケイリー木からケイリーグラフへの射に対応する。これは（代数的トポロジーでは）ケイリーグラフの一般には単連結とは限らない普遍被覆と解釈することもできる。

参考文献

• テンプレート:Cite book (self-archive)
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• 頂点推移グラフ
• 群の生成集合
• Lovász予想
• Cube-connected cycles
• 代数的グラフ理論
• 巡回グラフ
• ケイリーの定理

外部リンク

• Cayley diagrams
• テンプレート:Mathworld

テンプレート:Normdaten