Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 29, 2016 - 2:30pm

John Pike

Cornell

Location

University of Pennsylvania

DRL 3C8

Given a simple connected graph $G=(V,E)$, the abelian sandpile Markov chain evolves by adding chips to random vertices and then stabilizing according to certain toppling rules. The recurrent states form an abelian group $\Gamma$, the sandpile group of $G$.

I will discuss joint work with Dan Jerison and Lionel Levine in which we characterize the eigenvalues and eigenfunctions of the chain restricted to $\Gamma$ in terms of ``multiplicative harmonic functionsA'A' on $V$. We show that the moduli of the eigenvalues are determined up to a constant factor by the lengths of vectors in an appropriate dual Laplacian lattice and use this observation to bound the mixing time of the sandpile chain in terms of the number of vertices and maximum vertex degree of $G$. We also derive a surprising inverse relationship between the spectral gap of the sandpile chain and that of simple random walk on $G$.