Computing reduced divisors on finite graphs, and some applications

Series: 
Combinatorics Seminar
Friday, October 2, 2009 - 15:05
1 hour (actually 50 minutes)
Location: 
Skiles 255
,  
Georgia Tech
,  
Organizer: 
It is known that, relative to any fixed vertex q of a finite graph, there exists a unique q-reduced divisor (G-Parking function based at q) in each linear equivalence class of divisors. In this talk, I will give an efficient algorithm for finding such reduced divisors. Using this, I will give an explicit and efficient bijection between the Jacobian group and the set of spanning trees of the graph. Then I will outline some applications of the main results, including a new approach to the Random Spanning Tree problem, efficient computation of the group law in the critical and sandpile group, efficient algorithm for the chip-firing game of Baker and Norine, and the relation to the Riemann-Roch theory on finite graphs.