CoEulerian graphs
HTML articles powered by AMS MathViewer
- by Matthew Farrell and Lionel Levine
- Proc. Amer. Math. Soc. 144 (2016), 2847-2860
- DOI: https://doi.org/10.1090/proc/12952
- Published electronically: December 21, 2015
Abstract:
We suggest a measure of “Eulerianness” of a finite directed graph and define a class of “coEulerian” graphs. These are the graphs whose Laplacian lattice is as large as possible. As an application, we address a question in chip-firing posed by Björner, Lovász, and Shor in 1991, who asked for “a characterization of those digraphs and initial chip configurations that guarantee finite termination.” Björner and Lovász gave an exponential time algorithm in 1992. We show that this can be improved to linear time if the graph is coEulerian, and that the problem is $\textsf {NP}$-complete for general directed multigraphs.References
- David J. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math. 3 (1990), no. 4, 450–465. MR 1069105, DOI 10.1137/0403039
- Omid Amini and Madhusudan Manjunath, Riemann-Roch for sub-lattices of the root lattice $A_n$, Electron. J. Combin. 17 (2010), no. 1, Research Paper 124, 50. MR 2729373, DOI 10.37236/396
- Arash Asadi and Spencer Backman, Chip-firing and Riemann-Roch theory for directed graphs, Electronic Notes Discrete Math. 38 (2011), 63–68. arXiv:1012.0287
- Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766–788. MR 2355607, DOI 10.1016/j.aim.2007.04.012
- Anders Björner and László Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305–328. MR 1203679, DOI 10.1023/A:1022467132614
- Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283–291. MR 1120415, DOI 10.1016/S0195-6698(13)80111-4
- Benjamin Bond and Lionel Levine, Abelian networks I. Foundations and examples, 2013. arXiv:1309.3445
- Benjamin Bond and Lionel Leivne, Abelian networks II. Halting on all inputs, Selecta Math., to appear, 2015. arXiv:1409.0169
- Andrei Broder, Generating random spanning trees. In Symp. Foundations of Computer Sci., IEEE, New York, 442–447, 1989.
- Swee Hong Chan, Abelian sandpile model and Biggs-Merino polynomial for directed graphs, 2014. arXiv:1412.4837
- Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613–1616. MR 1044086, DOI 10.1103/PhysRevLett.64.1613
- P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50–59. MR 882842, DOI 10.1287/moor.12.1.50
- Kimmo Eriksson, No polynomial bound for the chip firing game on directed graphs, Proc. Amer. Math. Soc. 112 (1991), no. 4, 1203–1205. MR 1065944, DOI 10.1090/S0002-9939-1991-1065944-3
- M. A. Frumkin, Polynomial time algorithms in the theory of linear Diophantine equations, Fundamentals of computation theory (Proc. Internat. Conf., Poznań-Kórnik, 1977) Lecture Notes in Comput. Sci., Vol. 56, Springer, Berlin, 1977, pp. 386–392. MR 0502229
- James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI 10.1137/0220067
- C. Hermite, Sur l’introduction des variables continues dans la théorie des nombres, J. Reine Angew. Math. 41 (1851), 191–216 (French). MR 1578717, DOI 10.1515/crll.1851.41.191
- Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR 2477390, DOI 10.1007/978-3-7643-8786-0_{1}7
- Viktor Kiss and Lilla Tóthmérész, Chip-firing games on Eulerian digraphs and $\mathbf {NP}$-hardness of computing the rank of a divisor on a graph, Discrete Appl. Math. 193 (2015), 48–56. MR 3371611, DOI 10.1016/j.dam.2015.04.030
- Lionel Levine, Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Comm. Math. Phys. 335 (2015), no. 2, 1003–1017. MR 3316648, DOI 10.1007/s00220-014-2216-5
- David Perkinson, Jacob Perlman, and John Wilmes, Primer for the algebraic geometry of sandpiles, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211–256. MR 3204273, DOI 10.1090/conm/605/12117
- Kévin Perrot and Trung Van Pham, Chip-firing and partial Tutte polynomial for Eulerian digraphs, 2013. arXiv:1306.0294
- Trung Van Pham, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, Adv. in Appl. Math. 70 (2015), 45–53. MR 3388864, DOI 10.1016/j.aam.2015.06.006
- Günter Schaar, Remarks on Hamiltonian properties of powers of digraphs, Discrete Appl. Math. 51 (1994), no. 1-2, 181–186. 2nd Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1991). MR 1279633, DOI 10.1016/0166-218X(94)90107-4
- Eugene R. Speer, Asymmetric abelian sandpile models, J. Statist. Phys. 71 (1993), no. 1-2, 61–74. MR 1215850, DOI 10.1007/BF01048088
- Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
- Gábor Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math. 1 (1988), no. 3, 397–398. MR 955655, DOI 10.1137/0401039
- David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) ACM, New York, 1996, pp. 296–303. MR 1427525, DOI 10.1145/237814.237880
- Bohdan Zelinka, Centers of directed cacti, Časopis Pěst. Mat. 114 (1989), no. 3, 225–229 (English, with Russian and Czech summaries). MR 1016631, DOI 10.21136/CPM.1989.118370
Bibliographic Information
- Matthew Farrell
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14850
- Email: msf235@cornell.edu
- Lionel Levine
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14850
- MR Author ID: 654666
- Received by editor(s): May 26, 2015
- Received by editor(s) in revised form: September 2, 2015, and September 4, 2015
- Published electronically: December 21, 2015
- Additional Notes: This research was supported by NSF grants DMS-1243606 and DMS-1455272 and a Sloan Fellowship.
- Communicated by: Patricia L. Hersh
- © Copyright 2015 by the authors
- Journal: Proc. Amer. Math. Soc. 144 (2016), 2847-2860
- MSC (2010): Primary 05C05, 05C20, 05C45, 05C50, 68Q25
- DOI: https://doi.org/10.1090/proc/12952
- MathSciNet review: 3487219