Chip-Firing and Rotor-Routing on Directed Graphs
From MaRDI portal
Publication:3537737
zbMath1173.82339arXiv0801.3306MaRDI QIDQ3537737
James Propp, Alexander E. Holroyd, Karola Mészáros, Lionel Levine, Yuval Peres, David Bruce Wilson
Publication date: 10 November 2008
Full work available at URL: https://arxiv.org/abs/0801.3306
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite abelian groups (20K01) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)
Related Items
Indistinguishability of trees in uniform spanning forests, The distribution of sandpile groups of random graphs, Laplacian growth and sandpiles on the Sierpiński gasket: limit shape universality and exact solutions, Growth rates of groups associated with face 2-coloured triangulations and directed Eulerian digraphs on the sphere, Multi-Eulerian tours of directed graphs, Abelian networks. III: The critical group, Parking functions and tree inversions revisited, Sandpiles, Spanning Trees, and Plane Duality, Differential posets, Cayley graphs, and critical groups, Genus from sandpile torsor algorithm, Abelian networks IV. Dynamics of nonhalting networks, The Sandpile Cellular Automaton, Geometric bijections between spanning trees and break divisors, Exact computation and approximation of stochastic and analytic parameters of generalized Sierpinski gaskets, Principal specializations of Schubert polynomials and pattern containment, Applying the Kirchhoff relations in proofs of theorems on graph operations that do not affect the structure of the sandpile groups of graphs, The Range of a Rotor Walk, Robustness of the rotor-router mechanism, Abelian sandpile model and Biggs-Merino polynomial for directed graphs, Non-fixation for conservative stochastic dynamics on the line, Mean-field avalanche size exponent for sandpiles on Galton-Watson trees, Perfect boundaries in rotor-router aggregation on cylinders, Sandpile groups and spanning trees of directed line graphs, Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs, A greedy chip‐firing game, On Torsor Structures on Spanning Trees, A combinatorial mapping for the higher-dimensional matrix-tree theorem, Recurrence of horizontal-vertical walks, Abelian sandpiles on Sierpiński gasket graphs, Algorithmic aspects of rotor-routing and the notion of linear equivalence, A shape theorem for exploding sandpiles, Linear systems on tropical curves, Proppian random walks in \(\mathbb Z\), Integer superharmonic matrices on the \(F\)-lattice, Explicit deformation of lattice ideals via chip-firing games on directed graphs, A tropical proof of the Brill-Noether theorem, Critical groups for Hopf algebra modules, \(G\)-parking functions and tree inversions, Laplacian growth, sandpiles, and scaling limits, Compatible recurrent identities of the sandpile group and maximal stable configurations, The distribution of sandpile groups of random regular graphs, Minimal configurations and sandpile measures, Direction-reversing quasi-random rumor spreading with restarts, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, Asymptotic height distribution in high-dimensional sandpiles, \(R\)-systems, Critical group structure from the parameters of a strongly regular graph, On the sandpile group of the cone of a graph, A sandpile model for proportionate growth, Chip firing on Dynkin diagrams and McKay quivers, Proportionate growth in patterns formed in the rotor-router model, Spiral structures in the rotor-router walk, Reachability Switching Games, Sandpiles on the square lattice, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, The rotor-routing torsor and the Bernardi torsor disagree for every non-planar ribbon graph, Generators of invariant linear system on tropical curves for finite isometry group, Algebraic Properties of Generalized Graph Laplacians: Resistor Networks, Critical Groups, and Homological Algebra, Variation of Tamagawa numbers of Jacobians of hyperelliptic curves with semistable reduction, Chip-Firing and Riemann-Roch Theory for Directed Graphs, Height probabilities in the Abelian sandpile model on the generalized finite Bethe lattice, Infinite excursions of router walks on regular trees, The sandpile groups of chain-cyclic graphs, Chip-firing and energy minimization on M-matrices, Sandpiles and dominos, Limit linear series and the Amini-Baker construction, Learning about critical phenomena from scribbles and sandpiles, Differential posets and restriction in critical groups, Sandpile models, Combinatorial, piecewise-linear, and birational homomesy for products of two chains, Rotor Walks on Transient Graphs and the Wired Spanning Forest, CoEulerian graphs, Abelian Networks I. Foundations and Examples, Homomesy in products of two chains, A maximizing characteristic for critical configurations of chip-firing games on digraphs, Random walks with local memory, Enumerating linear systems on graphs, Sandpile groups and the join of graphs, Abelian Logic Gates, The sandpile group of a tree, A family of matrix-tree multijections, Rotor-routing reachability is easy, chip-firing reachability is hard, Infinite-step stationarity of rotor walk and the wired spanning forest, Degeneration of Linear Series from the Tropical Point of View and Applications, Determining Genus From Sandpile Torsor Algorithms, Convergence of the random abelian sandpile, Minimal free resolutions of the 𝐺-parking function ideal and the toppling ideal, Mixing time and eigenvalues of the abelian sandpile Markov chain, Unnamed Item, Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting, Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Directed nonabelian sandpile models on trees, Dynamic dimensional reduction in the abelian sandpile, On the complexity of the chip-firing reachability problem, Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs, Random integral matrices: universality of surjectivity and the cokernel
