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

Date

2021-05-01

Journal Title

Journal ISSN

Volume Title

Publisher

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.

Description

Keywords

Bijection, Combinatorics, Graph theory, Tutte polynomial, Parking function

Graduation Month

May

Degree

Doctor of Philosophy

Department

Department of Mathematics

Major Professor

Ilia Zharkov

Date

2021

Type

Dissertation

Citation