Loading...
Interval parking functions
Colaric, Emma DeMuse, Ryan Martin, Jeremy L. Yin, Mei
Colaric, Emma
DeMuse, Ryan
Martin, Jeremy L.
Yin, Mei
Citations
Altmetric:
Abstract
Interval parking functions (IPFs) are a generalization of ordinary parking functions in which each car is willing to park only in a fixed interval of spaces. Each interval parking function can be expressed as a pair (a, b), where a is a parking function and b is a dual parking function. We say that a pair of permutations (x,y) is reachable if there is an IPF (a,b) such that x, y are the outcomes of a, b, respectively, as parking functions. Reachability is reflexive and antisymmetric, but not in general transitive. We prove that its transitive closure, the pseudoreachability order, is precisely the bubble-sorting order on the symmetric group Sn, which can be expressed in terms of the normal form of a permutation in the sense of du Cloux; in particular, it is isomorphic to the product of chains of lengths 2,...,n. It is thus seen to be a special case of Armstrong’s sorting order, which lies between the Bruhat and (left) weak orders.
Description
Date
2020-11-16
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Collections
Files
Research Projects
Organizational Units
Journal Issue
Keywords
Parking function, Bubble-sort, Permutation, Bruhat order, Weak order
Citation
Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, Interval parking functions, Adv. Appl. Math. 123 (2021) 102129. https://doi.org/10.1016/j.aam.2020.102129