{
  "id": "1809.05774",
  "version": "v1",
  "published": "2018-09-15T21:43:06.000Z",
  "updated": "2018-09-15T21:43:06.000Z",
  "title": "On the growth of the Möbius function of permutations",
  "authors": [
    "Vít Jelínek",
    "Ida Kantor",
    "Jan Kynčl",
    "Martin Tancer"
  ],
  "comment": "34 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study the values of the M\\\"obius function $\\mu$ of intervals in the containment poset of permutations. We construct a sequence of permutations $\\pi_n$ of size $2n-2$ for which $\\mu(1,\\pi_n)$ is given by a polynomial in $n$ of degree 7. This construction provides the fastest known growth of $|\\mu(1,\\pi)|$ in terms of $|\\pi|$, improving a previous quadratic bound by Smith. Our approach is based on a formula expressing the M\\\"obius function of an arbitrary permutation interval $[\\alpha,\\beta]$ in terms of the number of embeddings of the elements of the interval into $\\beta$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-09-15T21:43:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05"
    ],
    "keywords": [
      "möbius function",
      "arbitrary permutation interval",
      "containment poset",
      "quadratic bound",
      "polynomial"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}