Generalized bijective maps between G-parking functions, spanning trees, and the Tutte polynomial

Abstract

We introduce an object called a tree growing sequence (TGS) in an effort to generalize bijective correspondences between G-parking functions, spanning trees, and the multiset of monomials of the Tutte polynomial of a graph G. A tree growing sequence determines an algorithm which can be applied to a single function, or to the set P[subscript G,q] of G-parking functions. When the latter is chosen, the algorithm uses splitting operations - inspired by the recursive definition of the Tutte polynomial - to partition P[subscript G,q]. The result of the TGS algorithm is a pair of bijective maps 𝜏 and ρ from P[subscript G,q] to the spanning trees of G and Tutte monomials, respectively. The algorithm can also be viewed as a way to classify maps 𝜏 that have a coherence property: the splitting operations give rise to a natural bijective map ρ from P[subscript G,q] to the multi-set of terms of T(G;x,y). We compare the TGS algorithm to Dhar's algorithm and the family of bijections found by Chebikin and Pylyavskyy in 2005, and obtain commutative diagrams to describe our comparisons. Additionally, we compute the Tutte polynomial of a zonotopal tiling using splitting operations analogous to those in the TGS algorithm.