Abstract: I will present heuristics and conjectures for sandpile groups of Erdos-Renyi random graphs that are closely related to the Cohen-Lenstra heuristics for class groups of quadratic number fields and predict, for instance, that the sandpile group of a random graph should be cyclic with probability equal to the product of the reciprocals of the Riemann zeta function evaluated at the odd integers 3, 5, 7, 9, etc. Many partial results on these conjectures have recently been proved by Melanie Wood.
Based on joint work with Julien Clancy, Nathan Kaplan, Timothy Leake, and Melanie Wood.
Abstract:
We investigate the rates at which we spread mass \(p\) of an initial unit mass
at a vertex \(v\), a distance \(\ge n\) away on various families of graphs. The process we use is as follows: at each time, we select a random site with positive mass and topple its mass equally to its neighbors.
Our initial motivation comes from the maximum overhang question in 1D case considered in Paterson-Peres-Thorup-Winkler-Zwick '09 which resolved a century old problem, but the more general case arises from optimal mass transport problems. On \(\mathbb{Z}^d\), we show that \(\Theta(n^{d+2})\) steps are necessary to move the mass, after we perform an initial `smoothing' of the mass over a ball of radius \(n/4\). We also consider a variant of the process, where we want to displace \(p=1/n\) mass on \(\mathbb{Z}^d\). For this, we show that the number of steps needed is \(\frac{n^{2+d}}{\log^2 n}\). On the comb graph, we show that we need \(\Theta(n^{7/2})\) steps.
For the case of trees with unit mass initially at the root, we show a bound of \(\Theta(d^n)\) for \(d\)-ary trees, and a bound of \(\Theta(n(\epsilon(d,l) + o(1))^n)\) on products of trees \(\mathbb{T}_d \times \mathbb{T}_l\), where \(\epsilon(d,l)\) depends only on the degrees \(d\) and \(l\) of the trees.
Finally, on graphs of bounded degree with exponential decay of Green functions, an example of which is the lamplighter group, we show that the number of steps to move the mass a distance \(n\) away grows exponentially in \(n\): \(\Theta(e^{cn})\), where \(c\) is a constant that does not depend on \(n\). Joint work with Yuval Peres.
Abstract: Associated to a graph there are three closely related ideals generated by powers of homogenous linear forms: the so-called external, central, and internal power ideals of the graph. These ideals come from various parts of math including Schubert calculus and approximation theory. The dimensions of the quotients by these ideals are T(2,1), T(1,1) and T(0,1) where T(x,y) is the Tutte polynomial of the graph. I will explain a bijection, based on Dhar's burning algorithm and partial orientations, between spanning forests of the graph and a linear basis of the quotient by the external power ideal that restricts to a bijection between spanning trees and a basis of the quotient by the central power ideal. This approach was essentially developed by Gessel-Sagan. Then I will suggest how recent work of Backman-Hopkins suggests this approach could be extended to the apparently more subtle internal case.
Abstract: An abelian processor is a finite automaton whose state transition and output do not depend on the order of input. An abelian *network* is a directed graph with an abelian processor at each vertex. I will define the critical group of an abelian network, and show how the sandpile group arises as a special case. This part is joint work with Ben Bond (http://arxiv.org/abs/1409.0170 ).
Next I’ll define the function computed by an abelian processor. For any finite abelian processor there is a network, built out of five simple components called “abelian logic gates”, that computes the same function. This part is joint work with Alexander Holroyd and Peter Winkler.
Finally, I will highlight three open questions:
Abstract: We will talk about the family of abelian networks that halt on all inputs, also known as halting networks. Classical examples of halting networks include the abelian sandpile model and the rotor-routing model with a sink. Associated to a halting network is the notion of recurrent classes and level function, which is a generalization of critical configurations and level function in sandpile model. We study the polynomial \(P(y)= \sum_{i} c_iy^{i}\), where \(c_i\) is the number of recurrent classes of a halting network with level \(i\). Merino's theorem states that for the sandpile model on an undirected graph, the polynomial \(P(y)\) is equal to the Tutte polynomial \(T(1,y)\) of the graph evaluated at \(x=1\), and a corollary of this theorem is that \(P(y)\) does not depend on the choice of sink of the sandpile. We prove a weak version of Merino's theorem for the halting network by showing that \(P(y)\) does not depend on the choice of sink of the network, which answers a conjecture of Perrot and Pham in the case of a sandpile model on a digraph. Furthermore, if the digraph is Eulerian, we generalize the full version of Merino's theorem by showing that \(P(y)\) is equal to the greedoid polynomial of the digraph.
Abstract: M-matrices generalize graph Laplacians and were shown by Gabrielov to yield avalanche finite systems. I will define and present various characterizations of this class of matrices. We will see how many aspects of graphical chip-firing (criticality, energy minimization and superstability) extend to this setting.
Furthermore, we propose a chip-firing model allowing for the redistribution dynamics to be governed by any invertible integer matrix L by pairing L with an M-matrix. The pairing changes the scope of valid configurations over which chip-firing occurs. This maintains the long term critical, superstable, and energy minimizing behavior of the classical model.
Joint work with Johnny Guzman.
Abstract: Two new classes of nonsingular M-matrices (or toppling or avalanche-finite) matrices, are studied from the point of view of their chip-firing/sandpile dynamics and their integer cokernels: the Cartan matrices of finite root systems, and the McKay-Cartan matrices for faithful representations of finite groups.
In the root system case, the recurrent configurations are identified explicitly, and related to minuscule dominant weights. In the McKay-Cartan case for finite subgroups G of special linear groups, the cokernel is related to the abelianization of G. In the case of the classical 2-dimensional McKay correspondence, the cokernel is isomorphic to the abelianization of G, or rather to its Pontrjagin dual.
Abstract: We show the relation of arithmetical graphs with the well know concept of M-matrices. Starting from this relation, we describe the arithmetical structures above the paths and cycles.
Abstract: Through three basic problems we present a panoramic view of the strong interaction between critical ideals and sandpile groups. Additionally we present some of the main problems in which we are interested.
Abstract: In this talk we introduce the problem of characterizing the graphs whose sandpile group has a fixed number of invariant factors, and discuss some techniques in which Critical Ideals give a method to understand the sandpile group.
Abstract: I will give a survey talk on the sandpile group of a graph, and its analogue for metric graphs, as it relates to tropical geometry. This will be an expository talk aimed at non-tropical-geometers.
Abstract: We present a summary of the results in our paper-in-progress Tropical analytic curves in 2-dimensional sandpile model (with Mikhail Shkolnikov). Details will be supplied in the following talk.
We study a sandpile model on the set of the lattice points in a large lattice polygon. A small perturbation \(\psi\) of the maximal stable state \(\mu\equiv 3\) is obtained by adding extra grains at several points. It appears, that the result \(\psi^\circ\) of the relaxation of \(\psi\) coincides with \(\mu\) almost everywhere; the set where \(\psi^\circ\ne \mu\) is called the deviation locus. The scaling limit of the deviation locus turns out to be a distinguished tropical curve passing through the perturbation points.
Then, instead of a large lattice polygon we can consider any convex domain \(\Omega\) and an analogous sandpile setup on the set of lattice points inside \(\Omega\). When the mesh of the lattice tends to zero, we again have a well-defined scaling limit of the deviation locus, which will be, in this case, a tropical analytical curve
Abstract: This talk provides details for the results in the previous talk. The proof consists of three main parts:
local considerations, properties of superharmonic integer-valued functions,
some dynamics on polytopes, piece-wise linear functions,
gluing procedures, interpretation of sand dynamics via polytope dynamics: the toppling function tends to a piecewise linear function \(F\), the deviation locus is exactly the place where the toppling function is not harmonic, that is, the corner locus of \(F\), that is, a tropical curve.
Abstract: We present tools for studying sandpiles with the mathematical software Sage.
Abstract: I will start with a general introduction to the theory of matroids. I will then focus on the class of regular matroids, and discuss how some ideas from chip-firing games extend from graphs to these matroids. For example, for such matroids one can define Jacobian groups whose cardinality/volume is related to the "complexity" of the matroid. I will end by introducing a very general class of bijections between Jacobian elements and bases elements. Although these bijections are described purely combinatorially, it turns out that there is a very beautiful geometry behind the scenes.
Abstract: I will explain how chip-firing can be viewed as the shadow of a certain process on partial graph orientations. I will then illustrate how this perspective lends itself to a more conceptual understanding of Baker and Norine's Riemann-Roch theorem for graphs.
Abstract: The rank of a divisor on a graph is a central notion in the discrete Riemann-Roch theory. We prove that the computation of this quantity is NP-hard. The computation of the rank can be translated to a question about a chip-firing game on an undirected graph. We prove the NP-hardness of this question by relating chip-firing on directed and undirected graphs. Joint work with Viktor Kiss.
Abstract: A well-known result of Kani and Rosen shows that the Jacobian of an algebraic curve with certain automorphism groups can be related to the Jacobians of the quotient curves by subgroups of automorphisms. In several recent papers, including one coauthored with Criel Merino, we have been able to show analogous results for the Jacobians of graphs. In particular, I will discuss the case where a graph G admits a harmonic action by a dihedral group and show the relationship between the Jacobian of G and the Jacobians of its quotient graphs.
Abstract: Consider an electrical resistor network. The Discrete Inverse Problem asks the following question: can the interior of the network be recovered by performing boundary measurements? Curtis-Ingerman-Morrow (1998) showed that the answer is 'yes' for critical circular planar networks. Recently, students at the University of Washington REU introduced a cohomology theory for measuring the obstruction to solvability of the Discrete Inverse Problem. Interpreting the sandpile group in terms of Q/Z-valued harmonic functions on a graph allows one to compute the sandpile group from this cohomology theory.
Abstract: In recent years several authors have considered Riemann-Roch theory in the context of commutative algebra, and in particular alexander duality of monomial ideals. In the case of RR on a graph G we have seen that certain chip-firing data is captured by a free resolution of these ideals supported on the graphical arrangement of G.
We generalize these constructions to the setting of tropical hyperplane arrangements, where the relevant monomial ideal is given by the underlying oriented matroid. Resolutions of these ideals are supported on the associated generalized permutohedron, where a choice of 'sink vertex' corresponds to viewing the polytope from an appropriate direction. This is joint work (in progress) with Raman Sanyal.
Abstract: The Jacobian group \(Jac(G)\) of a finite graph \(G\) is a group isomorphic to the sandpile group of \(G\), hence its cardinality is the number of spanning trees of \(G\). The graph \(G\) also has a tropical Jacobian which has the structure of a real torus; using the notion of break divisors, one can obtain a polyhedral decomposition of the tropical Jacobian where vertices and cells correspond to the elements of \(Jac(G)\) and the spanning trees of \(G\), respectively. In this talk I will give a combinatorial description to bijections coming from this geometric setting, I will also sketch how some previously known bijections can be related to these geometric bijections.