{
  "id": "1908.07277",
  "version": "v1",
  "published": "2019-08-20T11:28:34.000Z",
  "updated": "2019-08-20T11:28:34.000Z",
  "title": "Permutations with few inversions are locally uniform",
  "authors": [
    "David Bevan"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose ${\\boldsymbol\\sigma}$ is a permutation chosen uniformly at random from the set of all permutations of $[n]$ with exactly $m=m(n)\\ll n^2$ inversions. If $i<j$ are chosen uniformly at random from $[n]$, then ${\\boldsymbol\\sigma}(i)<{\\boldsymbol\\sigma}(j)$ asymptotically almost surely. However, if $i$ and $j$ are chosen so that $j-i\\ll m/n$, and $m \\ll n^2/\\log^2 n$, then $\\lim_{n\\to\\infty}\\mathbb{P}\\big[{\\boldsymbol\\sigma}(i)<{\\boldsymbol\\sigma}(j)\\big]=\\frac{1}{2}$. Moreover, if $k=k(n)\\ll \\sqrt{m/n}$, then the restriction of ${\\boldsymbol\\sigma}$ to a random $k$-point interval is asymptotically uniformly distributed over $\\mathcal{S}_k$. Thus, knowledge of the local structure of ${\\boldsymbol\\sigma}$ reveals nothing about its global form. We establish that $\\sqrt{m/n}$ is the threshold for local uniformity and $m/n$ the threshold for inversions, and determine the behaviour in the critical windows.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-08-20T11:28:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A16"
    ],
    "keywords": [
      "inversions",
      "locally uniform",
      "global form",
      "local structure",
      "point interval"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}