ケイリーグラフ

ふたつの元 a と b を生成元とする自由群 F₂ のケイリーグラフ

自由積 $Z_{2}*Z_{3}=\langle \,a,b\mid a^{2}=b^{3}=1\,\rangle$ のケイリーグラフ（PSL₂ Z）

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

定義

G を群、S をその生成集合とする。ケイリーグラフ Γ = Γ(G, S) とは以下のように構成されるグラフ彩色化有向グラフである：

• 群 G の各元 g に対して頂点を割り当てる：Γ の頂点集合 V(Γ) を G と同一視する。
• 生成集合 S の各元 s に対して色 c_s を割り当てる。
• 群 G の元 g と生成集合 S の元 s に対して元 g と gs に対応する頂点を色 c_s の有向辺でむすぶ。つまり辺集合 E(Γ) は (g, gs) の形をした組からなり、色は s ∈ S から定まる。

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

例

• 無限巡回群 G = Z と S として生成元 +1 とその逆元 −1 からなる集合を考えるとケイリーグラフは無限の道である。
• 同様に、位数 n の有限巡回群 G = Z_n と S として生成元とその逆元からなる集合を考えるとケイリーグラフは閉路 C_n である。より一般に、有限巡回群のケイリーグラフはちょうど circulant graphs に一致する。
• 直積群のケイリーグラフは対応するケイリーグラフの直積である。よって四元 (±1, 0), (0, ±1) を生成元とするアーベル群 Z² のケイリーグラフは平面 R² 上の無限格子であり、直積 Z_n × Z_m のケイリーグラフは同様の生成元をとるとトーラス上の n × m 有限格子である。

二面体群 D₄ の元 a と b を生成集合とするケイリーグラフ

D₄ の対合 b と c を生成集合とするケイリーグラフ

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

$D_{4}=\langle \,a,b\mid a^{4}=b^{2}=e,\ ab=ba^{3}\,\rangle$

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

$D_{4}=\langle \,b,c\mid b^{2}=c^{2}=e,\ bcbc=cbcb\,\rangle$

に対応する。

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

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

• 離散ハイゼンベルク群

$\left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}}:\ x,y,z\in \mathbb {Z} \right\}$

のケイリーグラフは右のように表される。生成元は成分 x, y, z における 1, 0, 0 の置換から与えられる三つの行列 X, Y, Z である。これらの生成元は図から読み取れる関係式 Z = XYX⁻¹Y⁻¹, XZ = ZX, YZ = ZY を満たす。この群は非可換無限群で三次元空間で表すことができ、ケイリーグラフは四次元の volume growth を持つ。

特徴づけ

群 G は自分自身に左からの乗算で作用する（ケイリーの定理を参照）。これは群 G がそのケイリーグラフに作用しているとみることができる。明示的には、元 h ∈ G は頂点 g ∈ V(Γ) を hg ∈ V(Γ) へ移す。ケイリーグラフの辺集合この作用で保たれる：辺 (g, gs) は辺 (hg, hgs) へ移される。群の左からの乗算による作用は単純推移的であり、とくにケイリーグラフは頂点推移的である。これは以下のケイリーグラフの特徴づけに繋がる：

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

ケイリーグラフ Γ = Γ(G, S) から群 G と生成集合 S を復元するには、まず頂点 v₁ ∈ V(Γ) を選び、群の単位元でラベルづける。そしてグラフ Γ の各頂点 v に対し、v₁ を v へ移す群 G のただひとつの元でラベルづける。生成集合が有限である必要十分条件はグラフが局所有限であることである。

基本的な性質

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

Schreier coset グラフ

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

群論とのつながり

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

幾何学的群論

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

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

歴史

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

ベーテ格子

→詳細は「ベーテ格子」を参照

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

参考文献

• Babai, László (1995). “Automorphism groups, isomorphism, reconstruction”. Handbook of Combinatorics. 2. Elsevier. pp. 1447–1540. ISBN 0-444-88002-X. MR1373683. Zbl 0846.05042. https://books.google.co.jp/books?id=5ktBP5vUl5gC&pg=PA1467  (self-archive)
• Gross, Jonathan L.; Tucker, Thomas W. (2001) [1987]. Topological Graph Theory. Dover. ISBN 0-486-41741-7. MR1855951. Zbl 0991.05001. https://books.google.co.jp/books?id=6HmA_x0dL9oC 
• Steinberg, Benjamin (2012). Representation Theory of Finite Groups: An Introductory Approach. Springer. ISBN 978-1-4614-0775-1. MR2867444. Zbl 1243.20001. https://books.google.co.jp/books?id=hKHrk6cti8YC 

関連項目

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

外部リンク

• Cayley diagrams
• Weisstein, Eric W. "Cayley graph". mathworld.wolfram.com (英語).