{
  "id": "1405.5587",
  "version": "v2",
  "published": "2014-05-22T01:22:01.000Z",
  "updated": "2014-09-07T20:11:21.000Z",
  "title": "Parking functions, Shi arrangements, and mixed graphs",
  "authors": [
    "Matthias Beck",
    "Ana Berrizbeitia",
    "Michael Dairyko",
    "Claudia Rodriguez",
    "Amanda Ruiz",
    "Schuyler Veeneman"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The \\emph{Shi arrangement} is the set of all hyperplanes in $\\mathbb R^n$ of the form $x_j - x_k = 0$ or $1$ for $1 \\le j < k \\le n$. Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is $(n+1)^{n-1}$. An unrelated combinatorial concept is that of a \\emph{parking function}, i.e., a sequence $(x_1, x_2, ..., x_n)$ of positive integers that, when rearranged from smallest to largest, satisfies $x_k \\le k$. (There is an illustrative reason for the term \\emph{parking function}.) It turns out that the number of parking functions of length $n$ also equals $(n+1)^{n-1}$, a result due to Konheim and Weiss from 1966. A natural problem consists of finding a bijection between the $n$-dimensional Shi arragnement and the parking functions of length $n$. Stanley and Pak (1996) and Athanasiadis and Linusson 1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-22T01:22:01.000Z",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-09-07T20:11:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A19",
      "52C35"
    ],
    "keywords": [
      "parking functions",
      "mixed graphs",
      "shi arrangements",
      "natural problem consists",
      "dimensional shi arragnement"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.5587B"
    }
  }
}