{
  "id": "2003.05935",
  "version": "v1",
  "published": "2020-03-12T17:59:21.000Z",
  "updated": "2020-03-12T17:59:21.000Z",
  "title": "Fertility Monotonicity and Average Complexity of the Stack-Sorting Map",
  "authors": [
    "Colin Defant"
  ],
  "comment": "16 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal D_n$ denote the average number of iterations of West's stack-sorting map $s$ that are needed to sort a permutation in $S_n$ into the identity permutation $123\\cdots n$. We prove that \\[0.62433\\approx\\lambda\\leq\\liminf_{n\\to\\infty}\\frac{\\mathcal D_n}{n}\\leq\\limsup_{n\\to\\infty}\\frac{\\mathcal D_n}{n}\\leq \\frac{3}{5}(7-8\\log 2)\\approx 0.87289,\\] where $\\lambda$ is the Golomb-Dickman constant. Our lower bound improves upon West's lower bound of $0.23$, and our upper bound is the first improvement upon the trivial upper bound of $1$. We then show that fertilities of permutations increase monotonically upon iterations of $s$. More precisely, we prove that $|s^{-1}(\\sigma)|\\leq|s^{-1}(s(\\sigma))|$ for all $\\sigma\\in S_n$, where equality holds if and only if $\\sigma=123\\cdots n$. This is the first theorem that manifests a law-of-diminishing-returns philosophy for the stack-sorting map that B\\'ona has proposed. Along the way, we note some connections between the stack-sorting map and the right and left weak orders on $S_n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-12T17:59:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A20",
      "37E15"
    ],
    "keywords": [
      "average complexity",
      "fertility monotonicity",
      "trivial upper bound",
      "left weak orders",
      "wests lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}