Computing reduced divisors on finite graphs, and some applications

Combinatorics Seminar
Friday, October 2, 2009 - 15:05
1 hour (actually 50 minutes)
Skiles 255
Georgia Tech
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.