{
  "id": "2006.09321",
  "version": "v1",
  "published": "2020-06-16T17:05:46.000Z",
  "updated": "2020-06-16T17:05:46.000Z",
  "title": "Interval parking functions",
  "authors": [
    "Emma Colaric",
    "Ryan DeMuse",
    "Jeremy L. Martin",
    "Mei Yin"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "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 \\emph{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 \\emph{pseudoreachability order}, is precisely the bubble-sort order on the symmetric group $\\Sym_n$, 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,\\dots,n$. It is thus seen to be a special case of Armstrong's sorting order, which lies between the Bruhat and (left) weak orders.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-16T17:05:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "06A07"
    ],
    "keywords": [
      "interval parking function",
      "normal form",
      "symmetric group",
      "armstrongs sorting order",
      "special case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}