Parking Functions on Trees and Directed Graphs
Loading...
Date
2019-07-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A parking function can be thought of as a sequence of n drivers, each with a preferred parking space, wanting to park along a one-way street with n parking spaces. Each driver checks her preferred parking space and, if it is occupied, parks in the first available space afterwards. One may consider how the enumeration of these sequences changes if the “parking lot” is made more complex, a question whose solution this dissertation lays the foundations for and answers in the case of certain families of graphs. We begin by generalizing the underlying parking lot to a general digraph and give several equivalent characterizations.
We then start by building on recent work in the case that the parking lot is a tree with edges directed towards a root. We generalize the notions of “prime” and “increasing” parking functions to give enumerative results concerning both. Additionally, we consider one of the numerous statistics on classical parking functions, the number of drivers who park in their desired spot, and show that it connects these tree parking functions that are prime and those that are both increasing and prime. Finally, we consider miscellaneous results on various families of trees and enumerate a generalization of Dyck paths in the process
Description
Keywords
combinatorics, parking functions, trees