グラフから構成される群

グラフからは様々な群が構成される。 まず思い浮ぶのはグラフの automorphism group だろう。

  • graph の automorphism group

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

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

  • Frucht の定理

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

無限グラフについても, de Groot の [Gro59] や Sabidussi の [Sab60] がある。

別の群としては, Dhar [Dha90] と Lorenzini [Lor91] による sandpile group というアーベル群がある。名前の通り, sandpile model や parking function と関係がある。Levine の [Lev09] によると, critical group や Jacobian などと呼ばれることもあるらしい。

グラフから内積を持つ free Abel群, つまり lattice を作ることもできる。Su と Wagner の [SW10] である。彼等はlattice of integer flows と呼んでいる。

グラフのデータから作られた群で, よりトポロジーと関係の深いものとしては right-angled Artin group やグラフの braid群がある。

グラフの頂点が群でラベル付けされているときには, graph product of groups という群を作ることもできる。各群が全て \(\Z \) のとき right-angled Artin group になるので right-angled Artin group の拡張である。 Crisp と Laca [CL02] の §2 によると, E.R. Green の thesis で導入されたものらしい。Crisp と Laca は Hermiller と Meier の [HM95] を参照している。

  • graph product of groups

更に, 辺の上にも群が乗っている graph of groups という構造も考えられている。例えば, [Cal08] など。

  • graph of groups

群を量子群に替えた変種もある。Fima と Freslon の [FF14] で定義され, 調べられている。

  • graph of quantum groups

References

[Cal08]

Danny Calegari. “Surface subgroups from homology”. In: Geom. Topol. 12.4 (2008), pp. 1995–2007. arXiv: 0803.4137. url: http://dx.doi.org/10.2140/gt.2008.12.1995.

[CL02]

John Crisp and Marcelo Laca. “On the Toeplitz algebras of right-angled and finite-type Artin groups”. In: J. Aust. Math. Soc. 72.2 (2002), pp. 223–245. arXiv: math/9907026. url: https://doi.org/10.1017/S1446788700003876.

[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.

[Dha90]

Deepak Dhar. “Self-organized critical state of sandpile automaton models”. In: Phys. Rev. Lett. 64.14 (1990), pp. 1613–1616. url: http://dx.doi.org/10.1103/PhysRevLett.64.1613.

[FF14]

Pierre Fima and Amaury Freslon. “Graphs of quantum groups and K-amenability”. In: Adv. Math. 260 (2014), pp. 233–280. arXiv: 1307.5609. url: https://doi.org/10.1016/j.aim.2014.04.008.

[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.

[Gro59]

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

[HM95]

Susan Hermiller and John Meier. “Algorithms and geometry for graph products of groups”. In: J. Algebra 171.1 (1995), pp. 230–257. url: https://doi.org/10.1006/jabr.1995.1010.

[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.

[Lev09]

Lionel Levine. “The sandpile group of a tree”. In: European J. Combin. 30.4 (2009), pp. 1026–1035. arXiv: math/0703868. url: https://doi.org/10.1016/j.ejc.2008.02.014.

[Lor91]

Dino J. Lorenzini. “A finite group attached to the Laplacian of a graph”. In: Discrete Math. 91.3 (1991), pp. 277–282. url: http://dx.doi.org/10.1016/0012-365X(90)90236-B.

[Sab60]

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

[SW10]

Yi Su and David G. Wagner. “The lattice of integer flows of a regular matroid”. In: J. Combin. Theory Ser. B 100.6 (2010), pp. 691–703. arXiv: 0908.4071. url: https://doi.org/10.1016/j.jctb.2010.07.003.