Parking Functions and Friends

12/03/2013 - 1:00am
Matthias Beck, San Francisco State University

Imagine a one-way cul-de-sac with four parking spots. Initially they are all free, but there are four cars approaching the street, and they would all like to park. To make life interesting, every car has a parking preference, and we record the preferences in a sequence of four numbers; e.g., the sequence (2, 1, 1, 3) means that the first car would like to park at spot number 2, the second and third drivers prefer parking spot number 1, and the last car would like to part at slot number 3. The street is very narrow, so there is no way to back up. Now each car enters the street and approaches its preferred parking spot; if it is free, it parks there, and if not, it moves down the street to the first available spot. We call a sequence a parking function if all cars end up finding a parking spot. For example, our sequence (2, 1, 1, 3) is a parking function, whereas (1, 3, 3, 4) is not.
Naturally, we could ask about parking functions for any number of parking spots; we call this number the length of the parking function. A moment's thought reveals that there is one parking function of length 1, three parking functions of length 2, and sixteen parking functions of length 3. A beautiful theorem due to Konheim and Weiss says that there is a pattern to be found here: there are precisely (n+1)^{n-1} parking functions of length n. We will hint at a proof of this theorem and illustrate how it allows us to connect parking functions to seemingly unrelated objects, which happen to exhibit the same counting pattern: a certain set of hyperplanes in n-dimensional space first studied by Shi, and a certain family of mixed graphs, which we introduced in recent joint work with Ana Berrizbeitia, Michael Dairyko, Claudia Rodriguez, Amanda Ruiz, and Schuyler Veeneman.

Davidson Lecture Hall, CMC
6th_Atul_Vyas_Memorial_Lecture Flyer.pdf179.65 KB

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences