Geometric bijections between spanning trees and break divisors

摘要

The Jacobian group Jac(G) of a finite graph G is a group whose cardinality is the number of spanning trees of G. G also has a tropical Jacobian which has the structure of a real torus; using the notion of break divisors, An et al. obtained a polyhedral decomposition of the tropical Jacobian where vertices and cells correspond to elements of Jac(G) and spanning trees of G, respectively. We give a combinatorial description of bijections coming from this geometric setting. This provides a new geometric method for constructing bijections in combinatorics. We introduce a special class of geometric bijections that we call edge ordering maps, which have good algorithmic properties. Finally, we study the connection between our geometric bijections and the class of bijections introduced by Bernardi; in particular we prove a conjecture of Baker that planar Bernardi bijections are "geometric". We also give sharpened versions of results by Baker and Wang on Bernardi torsors. (c) 2017 Elsevier Inc. All rights reserved.