On Permutation Invariant Parking Sequences

August 3, 2022
Parking sequences are a generalization of parking functions in which cars can have different lengths and there are as many parking spots as the sum of the car lengths. A list of parking spot preferences is said to be a parking sequence for the given car lengths if all cars are able to park. A parking sequence is said to be permutation invariant if all of its rearrangements are parking sequences. While all parking functions (i.e., parking sequences given cars of unit length) are invariant, this is not the case for parking sequences. The overarching goal of this work is to provide necessary and sufficient conditions for a parking sequence to be invariant. While obtaining a full characterization remains elusive, we do so for a number of foundational cases. Our main result is a concise characterization of minimally invariant car lengths, wherein the only invariant parking sequence is the all ones preference list. We moreover provide a full characterization of invariant parking sequences given two and three cars. Lastly, we give alternate proofs of known results for constant and strictly increasing car lengths and derive certain closure properties of invariant parking sequences. We conclude with a conjecture regarding a Boolean formula for minimally invariant parking sequences with four cars, as well as open questions concerning invariance under subgroups of the permutation group and the computational complexity of characterizing invariant parking sequences in their full generality.
Supplementary Materials