Cayley Graph

Cayley graph とは, 生成元の集合 \(S\) が指定された群 \(G\) から, \(G\) の元を頂点とし, ある頂点が別の頂点に \(S\) の元をかけて得られているとき, 辺で結ぶことによりで作られたグラフである。 Geometric group theory の基本的な道具である。

Cayley graph については, Tao の blog に 解説があるので, まずそれを読んでみるのがよいと思う。

どっちの元にどの生成元をかけてもう一つの元が得られるか, という情報まで含めると, 生成元の集合で辺がラベル付けられた quiver が得られるが, 普通 Cayley graph と言ったときには, 辺の向きやラベル付けを忘れたものを指すようである。

生成元の集合が指定された群としてまず思い浮かぶのが, Coxeter group であるが, Coxeter system を Cayley graph を用いて特徴付けることもできる。Michael Daivs の本 [Dav08] で述べられている。それを元に graph を hypergraph に代えたのが Radcliffe [Rad] の hyperreflection group である。

• Cayley hypergraph

Cayley hypergraph は, Lee と Kwon の [LK13] でも, 微妙に異なるものが定義されているが, 恐らく彼等は Radcliffe の定義を知らなかったのだろう。 彼等の Cayley hypergraph を元に, Yuan と Wang [YW] が Cayley dihypergraph というものを考えている。

Cayley graph の同型から群の同型が決まる群を CI-group というらしい。Li による survey [Li02] がある。

• CI-group

有限生成自由Abel群が CI-group であることは, Möller と Seifter [MS98] や Ryabchenko [Rya07] により証明された。一般の有限生成Abel群では CI-group ではないものが存在するようである。ただ, Löh [Löh13] が rank や torsion part の order は Cayley graph で決まることを示している。

Cayley graph が平面グラフになるような生成元が取れる群を planar group という。Knauer と Knauer の [KK]によると, 有限な planar group の特徴付けを発見したのは Maschke [Mas96] らしい。

Knauer と Knauer は, semigroup での類似を考えている。

• semigroup の Cayley graph

もちろん, semigroup 全般を考えるのは大変であるが, 彼等は right group という群に近い semigroup の class を考えている。

References

[Dav08]

Michael W. Davis. The geometry and topology of Coxeter groups. Vol. 32. London Mathematical Society Monographs Series. Princeton, NJ: Princeton University Press, 2008, pp. xvi+584. isbn: 978-0-691-13138-2; 0-691-13138-4.

[KK]

Kolja Knauer and Ulrich Knauer. On planar right groups. arXiv: 1309.5236.

[Li02]

Cai Heng Li. “On isomorphisms of finite Cayley graphs—a survey”. In: Discrete Math. 256.1-2 (2002), pp. 301–334. url: https://doi.org/10.1016/S0012-365X(01)00438-1.

[LK13]

Jaeun Lee and Young Soo Kwon. “Cayley hypergraphs and Cayley hypermaps”. In: Discrete Math. 313.4 (2013), pp. 540–549. url: https://doi.org/10.1016/j.disc.2012.11.022.

[Löh13]

Clara Löh. “Which finitely generated Abelian groups admit isomorphic Cayley graphs?” In: Geom. Dedicata 164 (2013), pp. 97–111. arXiv: 1202.5484. url: https://doi.org/10.1007/s10711-012-9761-x.

[Mas96]

H. Maschke. “The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley’s Color Diagrams”. In: Amer. J. Math. 18.2 (1896), pp. 156–194. url: http://dx.doi.org/10.2307/2369680.

[MS98]

Rögnvaldur G. Möller and Norbert Seifter. “Digraphical regular representations of infinite finitely generated groups”. In: European J. Combin. 19.5 (1998), pp. 597–602. url: https://doi.org/10.1006/eujc.1998.0210.

[Rad]

David G. Radcliffe. Hyperreflection groups. arXiv: 1008.1084.

[Rya07]

A. A. Ryabchenko. “Isomorphisms of Cayley graphs of a free abelian group”. In: Sibirsk. Mat. Zh. 48.5 (2007), pp. 1142–1146. url: https://doi.org/10.1007/s11202-007-0094-1.

[YW]

Kai Yuan and Yan Wang. Cayley dihypergraph and its automorphism group. arXiv: 2106.09561.