CoEulerian graphs

Farrell, Matthew; Levine, Lionel

doi:10.1090/proc/12952

CoEulerian graphs
HTML articles powered by AMS MathViewer

by Matthew Farrell and Lionel Levine PDF

Proc. Amer. Math. Soc. 144 (2016), 2847-2860

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