Automorphism Groups of Graphs

グラフから作られる群としてまず思い浮ぶのは, グラフの automorphism group だろう。

Krasikov と Lev と Thatte の [KLT02] によると, その位数の upper bound については文献がないそうである。この論文が初めての文献ということか。

この MathOverflow の質問によると, 任意の 有限群が有限 グラフの automorphism group として表せるということは, Frucht [Fru39] により証明されたらしい。

• Frucht の定理

この結果は, Costoya と Viruel [CV14] により, 有限群を self-homotopy equivalence の成す群として実現するのに用いられている。

無限グラフについても, de Groot の [Gro59] や Sabidussi の [Sab60] がある。 つまり, どんな群もグラフの automorphism group として実現できるということである。このことを, 次のように表現する。

• グラフの圏は universal category である。

Gromada の [Gro23] によると, グラフの quantum symmetry の研究は, Bichon の [Bic03] から始まったようである。

• quantum automorphism group

References

[Bic03]

Julien Bichon. “Quantum automorphism groups of finite graphs”. In: Proc. Amer. Math. Soc. 131.3 (2003), 665–673 (electronic). arXiv: math/9902029. url: http://dx.doi.org/10.1090/S0002-9939-02-06798-9.

[CV14]

Cristina Costoya and Antonio Viruel. “Every finite group is the group of self-homotopy equivalences of an elliptic space”. In: Acta Math. 213.1 (2014), pp. 49–62. arXiv: 1106.1087. url: https://doi.org/10.1007/s11511-014-0115-4.

[Fru39]

R. Frucht. “Herstellung von Graphen mit vorgegebener abstrakter Gruppe”. In: Compositio Math. 6 (1939), pp. 239–250. url: http://www.numdam.org/item?id=CM_1939__6__239_0.

[Gro23]

Daniel Gromada. “Quantum symmetries of Cayley graphs of abelian groups”. In: Glasg. Math. J. 65.3 (2023), pp. 655–686. arXiv: 2106.08787. url: https://doi.org/10.1017/s0017089523000198.

[Gro59]

J. de Groot. “Groups represented by homeomorphism groups”. In: Math. Ann. 138 (1959), pp. 80–102. url: https://doi.org/10.1007/BF01369667.

[KLT02]

Ilia Krasikov, Arieh Lev, and Bhalchandra D. Thatte. “Upper bounds on the automorphism group of a graph”. In: Discrete Math. 256.1-2 (2002), pp. 489–493. arXiv: math/0609425. url: http://dx.doi.org/10.1016/S0012-365X(02)00393-X.

[Sab60]

Gert Sabidussi. “Graphs with given infinite group”. In: Monatsh. Math. 64 (1960), pp. 64–67. url: https://doi.org/10.1007/BF01319053.