Wednesday, October 04, 2017 at 4:15pm to 5:15pm
SPEAKER: Chi Ho Yuen (Georgia Institute of Technology)
TITLE: Spanning Trees and Geometric Bijections
Associated to every graph G is a canonical finite abelian group Jac(G), called the Jacobian group, whose order is the number of spanning trees in G. The problem of giving a bijective proof for the equality # spanning trees = |Jac(G)| has received a considerable amount of interest, and various such bijections have been proposed. The focus of this talk is on how polyhedral geometry leads to a new 'geometric' family of such bijections. The geometric picture yields the following surprising connection: the previously discovered canonical group action for a plane graph (via rotor-routing or Bernardi process) is related to the canonical tropical geometric structure of its dual graph. If time permits, I will discuss a generalization to regular matroids and algorithmic aspects of the work. This is joint work with Spencer Backman and Matt Baker.