ケイリーグラフ

数学においてケイリーグラフ（）とは群の抽象的な構造を表現するアーサー・ケイリーの名に由来するグラフである。特定の（ふつうは有限な）群の生成集合に対して使われ、組合せ論的あるいは幾何学的群論における中心的な道具である。
定義.
 を群、 をその生成集合とする。ケイリーグラフ とは以下のように構成されるグラフ彩色化有向グラフである：
幾何学的群論ではふつう集合 は有限かつ対称（つまり ）であり、単位元を含まないと仮定する。このとき色を忘れたケイリーグラフは単純グラフである：辺に向きはなく、ループを含まない。
例.
に対応する。
特徴づけ.
群 は自分自身に左からの乗算で作用する（ケイリーの定理を参照）。これは群 がそのケイリーグラフに作用しているとみることができる。明示的には、元 は頂点 を へ移す。ケイリーグラフの辺集合この作用で保たれる：辺 は辺 へ移される。群の左からの乗算による作用は単純推移的であり、とくにケイリーグラフは頂点推移的である。これは以下のケイリーグラフの特徴づけに繋がる：
ケイリーグラフ から群 と生成集合 を復元するには、まず頂点 を選び、群の単位元でラベルづける。そしてグラフ の各頂点 に対し、 を へ移す群 のただひとつの元でラベルづける。生成集合が有限である必要十分条件はグラフが局所有限であることである。
Schreier coset グラフ.
頂点としてある固定した部分群 の右剰余類を取れば同種の構成——Schreier coset グラフ——を考えることができる。これは剰余類数え上げやTodd–Coxeterアルゴリズムの根底にある。
群論とのつながり.
群の構造に関する知識はグラフの隣接行列やとくにスペクトラルグラフ理論の定理を適用することで得ることができる。
幾何学的群論.
無限群に対してケイリーグラフのcoarse幾何学は幾何学的群論の基本である。有限生成群に対して、これは有限生成集合の選び方に依らず、したがってその群に固有の性質である。これは無限群に対してのみ興味のあることである：すべての有限群は全体を有限生成集合として選ぶことができるので一点（あるいは自明な群）とcoarse同値である。
形式的には、与えられた生成元に対して、語距離（ケイリーグラフ上の自然な距離）があり、距離空間を定める。この空間のcoarse同値の代表系は群の不変量である。
歴史.
ケイリーグラフは1878年にアーサー・ケイリーによって有限群に対して初めて考えられた。マックス・デーンは1909–1910年の群論に関する未刊行の講義録でGruppenbild (group diagram)という名前で再導入し、これが今日の幾何学的群論につながる。デーンの最も重要な応用は種数 の曲面の基本群に関する語の問題の解法で、これは曲面上の閉曲線が可縮かどうかを決定するという位相的な問題と等価である。
ベーテ格子.
ベーテ格子あるいはケイリー木は 個の生成元をもつ自由群のケイリーグラフである。 個の生成元をもつ群 の表示は 個の生成元をもつ自由群から群 への全射準同型と対応し、ケイリーグラフの観点からはケイリー木からケイリーグラフへの射に対応する。これは（代数的トポロジーでは）ケイリーグラフの一般には単連結とは限らない普遍被覆と解釈することもできる。