Spencer Backman Defense Dissertation

Chip-firing is a deceptively simple game played on the vertices of a graph, which was independently discovered in probability theory, poset theory, graph theory, and statistical physics. In recent years, chip-firing has been employed in the development of a theory of divisors on graphs analogous to the classical theory for Riemann surfaces. In particular, Baker and Norin were able to use this setup to prove a combinatorial Riemann-Roch formula, whose classical counterpart is one of the cornerstones of modern algebraic geometry. It is now understood that the relationship between divisor theory for graphs and algebraic curves goes beyond pure analogy, and the primary operation for making this connection precise is tropicalization, a certain type of degeneration which allows us to treat graphs as "combinatorial shadows" of curves. This tropical relationship between graphs and algebraic curves has led to beautiful applications of chip-firing to both algebraic geometry and number theory.

In this thesis we continue the combinatorial development of divisor theory for graphs.

Riemann-Roch Theory via Partial Graph Orientations: We introduce a new framework for investigating linear equivalence of divisors on graphs using a generalization of Gioan's cycle-cocycle reversal system for partial orientations. An oriented version of Dhar's burning algorithm is introduced and employed in the study of acyclicity for partial orientations. We then show that the Baker-Norin rank of a partially orientable divisor is one less than the minimum number of directed paths which need to be reversed in the generalized cycle-cocycle reversal system to produce an acyclic partial orientation. These results are applied in providing new proofs of the Riemann-Roch theorem for graphs as well as Luo's topological characterization of rank-determining sets. We demonstrate that max-flow min-cut is equivalent to the Euler characteristic description of orientable divisors, and generalize this characterization for partial orientations. Efficient algorithms for computing break divisors and constructing partial orientations are presented. We conclude with a description of the ways in which these results extend to the setting of partial orientations of metric graphs.

Transfinite Chip-Firing: We demonstrate that the greedy algorithm for reduction of divisors on metric graphs need not terminate by modeling the Euclidean algorithm with a divisor of degree 13 on a graph of genus 7, and running this example on a pair of incommensurable numbers. We observe that any infinite reduction has a well-defined limit, allowing us to treat the greedy reduction algorithm as a transfinite algorithm and analyze its running time via ordinal numbers. We prove by explicit construction that the set of running times for this algorithm is precisely the set of ordinals strictly less than \omega^\omega, and show that the running time for a given divisor D is bounded above by \omega^{deg(D)}.

Chip-Firing Induced by Open Covers: Given a graph G, a sink vertex v_0, and an abstract simplicial complex \sigma on the nonsink vertices of G, we define a hereditary chip-firing model by requiring that only vertices which form a face of \sigma may fire simultaneously. These models give a fine interpolation between the Abelian sandpile model, where \sigma is a disjoint collection of points, and the unconstrained chip-firing model, where \sigma is the full simplex. Hereditary chip-firing models retain some very desirable properties, e.g. stabilization is independent of firings chosen and each chip-firing equivalence class contains a unique recurrent configuration. These models turn out to be equivalent to the ones independently discovered by the physicist Paoletti, and we explain how this framework generalizes to directed graphs using weighted abstract simplicial complexes. An explicit bijection between the recurrent configurations of a hereditary chip-firing model on an undirected graph G and the spanning trees of G is presented which generalizes the Cori-Le Borgne algorithm. We give a description of how the basic results extend to metric graphs, where abstract simplicial complexes are replaced by open covers of \Gamma, and prove that any two to one cover of \Gamma by stars serves as a continuous analogue of the sandpile model admitting a duality with the unconstrained chip-firing model, which is strikingly similar to Riemann-Roch.

Chip-Firing and Riemann-Roch Theory for Directed Graphs and Arithmetical Graphs: The Riemann-Roch criteria of Amini and Manjunath is extended to all integer lattices orthogonal to some positive vector. Using generalized notions of v_0-reduced divisors and Dhar's algorithm, we investigate two chip-firing games coming from the rows and columns of the Laplacian of a strongly connected directed graph. We discuss how the "column" chip-firing game is related to directed \vec{G}-parking functions and the "row" chip-firing game is related to the directed sandpile model. Wilmes' lattice reduction algorithm shows that the "row" chip-firing game gives a graph theoretic model for the work of Amini and Manjunath. We conclude with a discussion of arithmetical graphs, which after a simple transformation may be viewed as a special class of directed graphs which will always have the Riemann-Roch property for the column chip-firing game. We answer a question of Lorenzini who asked for a combinatorial proof of the fact that if there are g_0 chips present in an arithmetical graph, then there exists a sequence of chip-firing moves which brings all of the vertices out of debt. Examples of arithmetical graphs are provided demonstrating that either, both, or neither of the two Riemann-Roch conditions may be satisfied for the row chip-firing game. This is joint work with Arash Asadi.