Sandpile Group

Sandpile group とは, Dhar [Dha90] と Lorenzini [Lor91] によりグラフに対して定義された, アーベル群である。名前の通り, sandpile model や parking function と関係がある。Levine の [Lev09] によると, critical group や Jacobian などと呼ばれることもあるらしい。 Shokrieh の [Sho10] によると, 他にも avalanche group, critical group, Picard group などの呼び名があるらしい。

このように1つの数学的構造に様々な名前があるのは珍しい, と思う。 この理由は, 様々な分野で独立に発見されてきたからに他ならない。

• 統計物理での sandpile model
• chip-firing game
• parking function
• arithmetic geometry
• algebraic graph theory

Jacobian group や Picard group などといった名前は, 当然 Jacobian variety との類似から来たものである。

その位数が, spanning tree の個数と等しい, というのは, いわゆる Kirchhoff の matrix-tree theorem から分かる。

• matrix-tree theorem

正確には, matrix-tree theorem は, spanning tree の個数と reduced Laplacian の行列式が等しいことを言っているが, その行列式と sandpile group の位数が等しいのである。 このことから, sandpile group と spanning tree の集合の間に全単射を構成することが考えられるが, それについては Baker と Shokrieh の [BS13] とそこに挙げられている文献を見るとよい。

群と集合の間の全単射というと torsor を思い浮かべるが, torsor として考えられることを指摘したのは Jordan Ellenberg らしい。実際に, torsor の構造を証明したのは Holroyd ら [Hol+08] のようであるが。その torsor は rotor-routing torsor と呼ばれているが, 他にも Matthew Baker と Wang が Bernardi の仕事 [Ber08] に基づいて定義した Bernardi torsor というものもある。

• rotor-routing torsor
• Bernardi torsor

単体的複体をグラフの高次元版とみなすことにより, Duval と Klivans と Martin は [DKM11; DKM15] で単体的複体や胞体複体への一般化を定義し, 調べている。

他にも, 有限群の faithful representation に対しても, Benkart と Klivans と Reiner [BKR18] が sandpile group を定義している。

References

[Ber08]

Olivier Bernardi. “Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings”. In: Electron. J. Combin. 15.1 (2008), Research Paper 109, 53. arXiv: math/0612003. url: http://www.combinatorics.org/Volume_15/Abstracts/v15i1r109.html.

[BKR18]

Georgia Benkart, Caroline Klivans, and Victor Reiner. “Chip firing on Dynkin diagrams and McKay quivers”. In: Math. Z. 290.1-2 (2018), pp. 615–648. arXiv: 1601 . 06849. url: https://doi.org/10.1007/s00209-017-2034-5.

[BS13]

Matthew Baker and Farbod Shokrieh. “Chip-firing games, potential theory on graphs, and spanning trees”. In: J. Combin. Theory Ser. A 120.1 (2013), pp. 164–182. arXiv: 1107 . 1313. url: https://doi.org/10.1016/j.jcta.2012.07.011.

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

[DKM11]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Critical groups of simplicial complexes”. In: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011). Discrete Math. Theor. Comput. Sci. Proc., AO. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, pp. 269–280. arXiv: 1101. 3981.

[DKM15]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Cuts and flows of cell complexes”. In: J. Algebraic Combin. 41.4 (2015), pp. 969–999. arXiv: 1206.6157. url: https://doi.org/10.1007/s10801-014-0561-2.

[Hol+08]

Alexander E. Holroyd et al. “Chip-firing and rotor-routing on directed graphs”. In: In and out of equilibrium. 2. Vol. 60. Progr. Probab. Basel: Birkhäuser, 2008, pp. 331–364. arXiv: 0801.3306. url: http://dx.doi.org/10.1007/978-3-7643-8786-0_17.

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

[Sho10]

Farbod Shokrieh. “The monodromy pairing and discrete logarithm on the Jacobian of finite graphs”. In: J. Math. Cryptol. 4.1 (2010), pp. 43–56. arXiv: 0907 . 4764. url: https://doi.org/10.1515/JMC.2010.002.