ケイリーグラフとは？ わかりやすく解説

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

• 離散ハイゼンベルク群

${\displaystyle \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 の単純推移的な作用を持つことである^[3]。

ケイリーグラフ Γ = Γ(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 はある。もし生成集合が極小ならば、頂点連結度は次数と等しい。辺連結度はどんな場合でも次数と等しい^[4]。
• 有限アーベル群 G のケイリーグラフ Γ(G, S) が定める隣接行列の固有値は、既約指標 χ を用いて λ_χ = ∑_{s ∈ S} χ(s) と表せる^[5]。また各固有値に属する固有ベクトルも既約指標の値を並べることで得られる。

Schreier coset グラフ

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

群論とのつながり

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

幾何学的群論

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

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

歴史

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

ベーテ格子

ベーテ格子あるいはケイリー木は 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.com/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.com/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.com/books?id=hKHrk6cti8YC 

関連項目

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

外部リンク

• Cayley diagrams
• Weisstein, Eric W. "Cayley graph". MathWorld (英語).