Date:
Mon, 28/05/201811:00-12:30
Location:
IIAS, Eilat hall, Feldman bldg, Givat Ram
Speaker: Daniel Jarison, TAU
Title: Random walks on sandpile groups
Abstract:
The sandpile group of a finite graph is an abelian group that is defined using the graph Laplacian. Its elements are the recurrent configurations of the "chip-firing game" on the graph. I will describe a natural random walk on this group. The main questions are: how long does it take for the sandpile random walk to mix, and how is the mixing time related to the geometry of the underlying graph? These questions can sometimes be answered even if the actual group is unknown. In particular, the spectral gaps of the sandpile walk and of the simple random walk on the underlying graph exhibit a surprising inverse relationship. In certain cases, the sandpile walk exhibits "cutoff" behavior: the Markov chain goes from almost completely unmixed to almost completely mixed in a relatively short number of steps. I will give a tour of what we know about the sandpile walk and briefly discuss how some of the results are proved.
This is joint work with Bob Hough, Lionel Levine, and John Pike.
Title: Random walks on sandpile groups
Abstract:
The sandpile group of a finite graph is an abelian group that is defined using the graph Laplacian. Its elements are the recurrent configurations of the "chip-firing game" on the graph. I will describe a natural random walk on this group. The main questions are: how long does it take for the sandpile random walk to mix, and how is the mixing time related to the geometry of the underlying graph? These questions can sometimes be answered even if the actual group is unknown. In particular, the spectral gaps of the sandpile walk and of the simple random walk on the underlying graph exhibit a surprising inverse relationship. In certain cases, the sandpile walk exhibits "cutoff" behavior: the Markov chain goes from almost completely unmixed to almost completely mixed in a relatively short number of steps. I will give a tour of what we know about the sandpile walk and briefly discuss how some of the results are proved.
This is joint work with Bob Hough, Lionel Levine, and John Pike.