×

zbMATH — the first resource for mathematics

Chip-firing games and critical groups. (English) Zbl 1447.05135
Harris, Pamela E. (ed.) et al., A project-based guide to undergraduate research in mathematics. Starting and sustaining accessible undergraduate research. Cham: Birkhäuser. Found. Undergrad. Res. Math., 107-152 (2020).
Summary: In this note we introduce a finite abelian group that can be associated with any finite connected graph. This group can be defined in an elementary combinatorial way in terms of chip-firing operations, and has been an object of interest in combinatorics, algebraic geometry, statistical physics, and several other areas of mathematics. We will begin with basic definitions and examples and develop a number of properties that can be derived by looking at this group from different angles. Throughout, we will give exercises, some of which are straightforward and some of which are open questions. We will also highlight some of the many contributions to this area made by undergraduate students.
For the entire collection see [Zbl 07183686].
MSC:
05C57 Games on graphs (graph-theoretic aspects)
05C40 Connectivity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
91A43 Games involving graphs
20K01 Finite abelian groups
Software:
jacobians
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Carlos A. Alfaro and Carlos E. Valencia, On the Sandpile group of the cone of a graph, Linear Algebra Appl. 436 (2012), no. 5, 1154-1176. · Zbl 1236.05131
[2] Omid Amini and Janne Kool, A spectral lower bound for the divisorial gonality of metric graphs, Int. Math. Res. Not. IMRN (2016), no. 8, 2423-2450. · Zbl 1404.58042
[3] Yang An, Matthew Baker, Greg Kuperberg, and Farbod Shokrieh, Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem, Forum Math. Sigma 2 (2014), e24, 25 pp. · Zbl 1306.05013
[4] Kassie Archer, Abby Bishop, Alexander Diaz Lopez, Luis David García Puente, Darren Glass, and Joel Louwsma, Arithmetical structures on bidents, To appear in Discrete Math. https://arxiv.org/abs/1903.01393, 2019. · Zbl 1440.05137
[5] Arash Asadi and Spencer Backman, Chip-firing and Riemann-Roch theory for directed graphs, https://arxiv.org/abs/1012.0287v2, (2011). · Zbl 1274.05189
[6] Roland Bacher, Pierre de la Harpe, and Tatiana Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France 125 (1997), no. 2, 167-198. · Zbl 0891.05062
[7] Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766-788. · Zbl 1124.05049
[8] Matthew Baker and Serguei Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not. IMRN (2009), no. 15, 2914-2955. · Zbl 1178.05031
[9] Matthew Baker and Farbod Shokrieh, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A 120 (2013), no. 1, 164-182. · Zbl 1408.05089
[10] Ryan Becker and Darren Glass,Cyclic Critical Groups of Graphs, Austral. Jour. of Comb. 64 (2016), 366-375. · Zbl 1333.05254
[11] Andrew Berget, Andrew Manion, Molly Maxwell, Aaron Potechin, and Victor Reiner,The critical group of a line graph, Ann. Comb. 16 (2012), no. 3, 449-488. · Zbl 1256.05095
[12] Kenneth Berman, Bicycles and spanning trees, SIAM J. Algebraic Discrete Methods 7 (1986), no. 1, 1-12. · Zbl 0588.05016
[13] Norman Biggs, Algebraic Graph Theory. Second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993. viii+205 pp.
[14] N. L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999), no. 1, 25-45. · Zbl 0919.05027
[15] Anders Björner and László Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305-328. · Zbl 0805.90142
[16] Siegfried Bosch and Dino Lorenzini, Grothendieck’s pairing on component groups of Jacobians, Invent. Math. 148 (2002), no. 2, 353-396. · Zbl 1061.14042
[17] David Brandfonbrener, Pat Devlin, Netanel Friedenberg, Yuxuan Ke, Steffen Marcus, Henry Reichard, and Ethan Sciamma,Two-vertex generators of Jacobians of graphs, Electr. J. Comb. 25 (2018), P1.15. · Zbl 1380.05098
[18] Benjamin Braun, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, and Carlos E. Valencia, Counting arithmetical structures on paths and cycles, Discrete Math. 341 (2018), no. 10, 2949-2963. · Zbl 1393.05152
[19] Morgan V. Brown, Jackson S. Morrow, and David Zureick-Brown, Chip-firing groups of iterated cones, Linear Algebra Appl. 556 (2018), 46-54. · Zbl 1394.05069
[20] David B. Chandler, Peter Sin, and Qing Xiang, The Smith and critical groups of Paley graphs, J. Algebraic Combin. 41 (2015), no. 4, 1013-1022. · Zbl 1316.05058
[21] Sheng Chen and Sheng Kui Ye, Critical groups for homeomorphism classes of graphs, Discrete Mathematics 309 (2009), no. 1, 255-258. · Zbl 1198.05088
[22] Fan R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.
[23] Mihai Ciucu, Weigen Yan, and Fuji Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005), no. 1, 105-116. · Zbl 1072.05038
[24] Julien Clancy, Nathan Kaplan, Timothy Leake, Sam Payne, and Melanie Matchett Wood,On a Cohen-Lenstra heuristic for Jacobians of random graphs, J. Algebraic Combin. 42 (2015), no. 3, 701-723. · Zbl 1325.05146
[25] Julien Clancy, Timothy Leake, and Sam Payne,A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs, Exp. Math. 24 (2015), no. 1, 1-7. · Zbl 1310.05121
[26] Anna Comito, Jennifer Garcia, Josefina Alvarado Rivera, Natalie L. F. Hobson, and Luis David Garcia Puente, On the Sandpile group of circulant graphs, 2016.
[27] Robert Cori and Y. Le Borgne. The Sandpile model and Tutte polynomials. Adv. in Appl. Math., 30 (2003), no. 1, 44-52. · Zbl 1030.05058
[28] Robert Cori and Dominique Rossin, On the Sandpile group of dual graphs, European J. Combin. 21 (2000), no. 4, 447-459. · Zbl 0969.05034
[29] F. Cools, J. Draisma, S. Payne, and E. Robeva,A tropical proof of the Brill-Noether theorem, Adv. Math. 230 (2012), no. 2, 759-776. · Zbl 1325.14080
[30] Hugo Corrales and Carlos E. Valencia, Arithmetical structures on graphs, Linear Algebra Appl. 536 (2018), 120-151. · Zbl 1428.05188
[31] ———, Arithmetical structures on graphs with connectivity one, J. Algebra Appl. 17 (2018), no. 8, 1850147, 13. · Zbl 1393.05177
[32] Scott Corry and David Perkinson, Divisors and Sandpiles: An introduction to chip-firing, American Mathematical Society, Providence, RI, 2018. · Zbl 1411.05003
[33] Josse van Dobben de Bruyn and Dion Gijswijt,Treewidth is a lower bound on graph gonality, https://arxiv.org/abs/1407.7055, 2014.
[34] Andrew Deveau, David Jensen, Jenna Kainic, and Dan Mitropolsky,Gonality of random graphs, Involve 9 (2016), no. 4, 715-720. · Zbl 1341.05227
[35] Joshua E. Ducey, Jonathan Gerhard, and Noah Watson,The Smith and Critical Groups of the Square Rook’s Graph and its Complement, Electr. J. Comb. 23 (2016), no. 4, P4.9. · Zbl 1351.05105
[36] Neelav Dutta and David Jensen,Gonality of expander graphs, Discrete Math.. 341 (2018), no. 9, 2535-2543. · Zbl 1392.05099
[37] Alan Frieze and Michał Karoński, Introduction to Random Graphs, Cambridge University Press, Cambridge, 2016. · Zbl 1328.05002
[38] Louis Gaudet, David Jensen, Dhruv Ranganathan, Nicholas Wawrykow, and Theodore Weisman,Realization of groups with pairing as Jacobians of finite graphs, Ann. Comb. 22 (2018), no. 4, 781-801. · Zbl 1403.05060
[39] Mark Giesbrecht, Fast computation of the Smith normal form of an integer matrix, Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA), ISSAC ’95, ACM, 1995, pp. 110-118. · Zbl 0915.65032
[40] Darren Glass and Criel Merino, Critical groups of graphs with dihedral actions, European J. Combin. 39 (2014), 95-112. · Zbl 1284.05124
[41] Gopal Goel and David Perkinson,Critical groups of iterated cones, Linear Algebra Appl. 567 (2019), 138-142. · Zbl 1411.05161
[42] Fernando Q. Gouvêa, p-adic Numbers: An introduction, second ed., Universitext, Springer-Verlag, Berlin, 1997. · Zbl 0874.11002
[43] Phillip A Griffiths and Joseph Harris, Principles of Algebraic Geometry, Wiley Classics Library, Wiley, New York, NY, 1994. · Zbl 0836.14001
[44] Yaoping Hou, Chingwah Woo, and Pingge Chen, On the Sandpile group of the square cycle Cn2, Linear Algebra Appl. 418 (2006), no. 2, 457-467. · Zbl 1108.05062
[45] Brian Jacobson, Andrew Niedermaier, and Victor Reiner,Critical groups for complete multipartite graphs and Cartesian products of complete graphs, Journal of Graph Theory 44 (2003), no. 3, 231-250. · Zbl 1031.05064
[46] Sameer Kailasa, Vivian Kuperberg, and Nicholas Wawrykow,Chip-firing on trees of loops. Electron. J. Combin. 25 (2018), no. 1, Paper 1.19, 12 pp. · Zbl 1418.14008
[47] Edward C. Kirby, Roger B. Mallion, Paul Pollak, and Paweł J. Skrzyński, What Kirchhoff actually did concerning spanning trees in electrical networks and its relationship to modern graph-theoretical work, Croatica Chemica Acta 89 (2016).
[48] Caroline Klivans, The Mathematics of Chip-Firing, Chapman and Hall/CRC, New York, 2018. · Zbl 1403.05003
[49] S. V. Konyagin, Double exponential lower bound for the number of representations of unity by Egyptian fractions, Math. Notes 95 (2014), no. 1-2, 277-281, Translation of Mat. Zametki 95 (2014), no. 2, 312-316. · Zbl 1320.11030
[50] Shaked Koplewitz, Sandpile groups and the Coeulerian property for random directed graphs, Adv. in Appl. Math. 90 (2017), 145-159. · Zbl 1366.05048
[51] ———, Sandpile groups of random bipartite graphs, https://arxiv.org/abs/1705.07519, 2017.
[52] Timothy Leake and Dhruv Ranganathan,Brill-Noether theory of maximally symmetric graphs, European J. Combin. 46 (2015), 115-125. · Zbl 1307.05121
[53] Chang Mou Lim, Sam Payne, and Natasha Potashnik,A note on Brill-Noether theory and rank determining sets for metric graphs, Int. Math. Res. Not. IMRN (2012), no. 23, 5484-5504. · Zbl 1328.14099
[54] Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481-501. · Zbl 0662.14008
[55] ———, Groups of components of Néron models of Jacobians, Compositio Math. 73 (1990), no. 2, 145-160. · Zbl 0737.14008
[56] ———, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), no. 3, 277-282. · Zbl 0755.05079
[57] ———, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271-1300. · Zbl 1175.05088
[58] Jessie MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly 76 (1969), 152-164. · Zbl 0186.33702
[59] A. D. Mednykh and I. A. Mednykh, On the structure of the Jacobian group of circulant graphs. (Russian) Dokl. Akad. Nauk 469 (2016), no. 5, 539-543; translation in Dokl. Math. 94 (2016), no. 1, 445-449 · Zbl 1350.05061
[60] ———, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic. Discrete Math. 342 (2019), no. 6, 1772-1781. · Zbl 1414.05080
[61] András Mészáros, The distribution of sandpile groups of random regular graphs, https://arxiv.org/abs/1806.03736v4, 2020.
[62] Rick Miranda, Nondegenerate symmetric bilinear forms on finite abelian 2-groups, Trans. Amer. Math. Soc. 284 (1984), no. 2, 535-542. · Zbl 0512.10014
[63] Hoi Nguyen and Melanie Matchett Wood, Random integral matrices: universality of surjectivity and the cokernel, https://arxiv.org/abs/1806.00596, 2018.
[64] Victor Reiner and Dennis Tseng,Critical groups of covering, voltage and signed graphs, Discrete Math. 318 (2014), 10-40. · Zbl 1281.05072
[65] J. Sedláček, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970), 515-517. · Zbl 0202.23501
[66] Farbod Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol. 4 (2010), no. 1, 43-56. · Zbl 1231.05173
[67] Daniel A. Spielman, Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.) 54 (2017), no. 1, 45-61. · Zbl 1351.05146
[68] Richard P. Stanley, Smith normal form in combinatorics, J. Combin. Theory Ser. A 144 (2016), 476-495. · Zbl 1343.05026
[69] Arne Storjohann, Near optimal algorithms for computing Smith normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation (New York, NY, USA), ISSAC ’96, ACM, 1996, pp. 267-274. · Zbl 0914.65043
[70] David G. Wagner, The critical group of a directed graph, https://arXiv:math/0010241, 2000.
[71] C. T. C. Wall, Quadratic forms on finite groups, and related topics, Topology 2 (1963), 281-298. · Zbl 0215.39903
[72] Melanie Matchett Wood, The distribution of sandpile groups of random graphs, J. Amer. Math. Soc. 30 (2017), no. 4, 915-958. · Zbl 1366.05098
[73] ———, Random integral matrices and the Cohen-Lenstra heuristics, Amer. · Zbl 1446.11170
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.