Speaker：Thomas Selig (Xi'an Jiaotong-Liverpool University)

Time：2024-6-24, 10:00

Location：Conference Room 686 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

In parking problems, a given number of cars enter a one-way street sequentially, and try to park according to a specified preferred spot in the street. When two cars have the same preferred spot, we say that a collision occurs. Different models are possible depending on the chosen rule for handling collisions. In this talk, we will study a variant called the MVP ("Most Valuable Player") model. In this, priority is given to later cars, as follows. When a car finds its preferred spot already occupied by a previous car, it bumps that car out of the spot and parks there. The previous car then drives forward in the street, and parks in the first available spot. An MVP parking function is an allocation of a preferred spot to each car which allows all cars to park according to this model.

We will study MVP parking functions according to their outcome permutation, which described the final order of the cars once they have all successfully parked. We exhibit rich combinatorial connections to a variety of objects such as permutation inversion graphs, Motzkin paths, non-crossing matchings, and more.