Discipline: Mathematics and Statistics
Subcategory: Mathematics and Statistics
Session: 3
Room: Exhibit Hall
Eric J. Pabon-Cancel - University of Puerto Rico, Mayagüez Campus
Co-Author(s): Douglas M. Chen, Johns Hopkins University, Baltimore, Maryland; Pamela E. Harris, University of Wisconsin-Milwaukee, Milwaukee, Wisconsin; J. Carlos Martínez Mori, Cornell University, Ithaca, New York; Gabriel Sargent, University of Notre Dame, South Bend, Indiana;
We introduce emph{parking assortments}, a generalization of parking functions in which there are $ninmathbb{N}$ cars of assorted lengths $mathbf{y}=(y_1,y_2,ldots,y_n)inmathbb{N}^n$ entering a one-way street containing $m=sum_{i=1}^ny_i$ parking spots.The cars have parking preferences $mathbf{x}=(x_1,x_2,ldots,x_n)in[m]^n$, where $[m]coloneqq{1,2,ldots,m}$, and enter the street in order.Each car $i in [n]$, with length $y_i$ and preference $x_i$, follows a natural extension of the classical parking rule: it begins looking for parking at its preferred spot $x_i$ and parks in the first $y_i$ contiguously available spots thereafter, if there are any.For a fixed $mathbf{y}$, if all cars are able to park under the preference list $mathbf{x}$, we say that $mathbf{x}$ is a emph{parking assortment} for $mathbf{y}$. In this way, parking assortments generalize parking functions, which correspond to the case in which $mathbf{y}$ is a list of all ones.Moreover, for a fixed $mathbf{y}$, the set of parking assortments contains the set of emph{parking sequences}, which correspond to the case in which car $i$ fails to park if, upon its arrival, the first available spot $j geq x_i$ is such that either $j+y_i-1>m$ or at least one of the subsequent spots $j+1,ldots,j+y_i-1$ is already occupied.\We say a parking assortment $mathbf{x}$ for $mathbf{y}$ is emph{permutation-invariant} (or emph{invariant} for short) if all of the rearrangements of $mathbf{x}$ are parking assortments for $mathbf{y}$.While all parking functions are invariant, this is not the case for parking assortments in general.The goal of this work is to provide necessary and sufficient conditions for parking assortments to be invariant for a fixed arbitrary $mathbf{y}$.While obtaining a full characterization for an arbitrary number of cars remains elusive, we do so for the case of two and three cars.Given the technicality of these results, we introduce the notion of emph{minimally invariant} car lengths, for which the only invariant parking assortment is the all ones preference list.We provide a concise, oracle-base characterization of minimally invariant car lengths for any number of cars and derive certain closure properties of this set.We conclude with a conjecture regarding a Boolean formula for minimally invariant parking assortments with four cars. We also pose open questions concerning invariance under subsets of the permutation group and the computational complexity of characterizing invariant parking assortments in their full generality.\
Funder Acknowledgement(s): This material is based upon work supported by the National Science Foundation under Grant No. DMS-1929284 while the authors were in residence at the Institute for Computational and Experimental Research in Mathematics.
Faculty Advisor: Pamela E. Harris, peharris@uwm.edu
Role: On this combinatorics project, I was in charge of exploring properties of permutation invariant parking sequences, a generalization of parking functions that allows parking of cars of different lengths. These combinatorial objects arose from hashing functions, which are widely used in computer science. I utilized SAGEMath to compute families of the permutation invariant parking sequences for 2-tuple vectors and 3-tuple vectors. These computations lead our research group to develop several theorems that provided us with a certain characterization of these mathematical objects.