{
  "id": "2012.13795",
  "version": "v1",
  "published": "2020-12-26T18:47:47.000Z",
  "updated": "2020-12-26T18:47:47.000Z",
  "title": "On the Möbius function of permutations under the pattern containment order",
  "authors": [
    "David Marchant"
  ],
  "comment": "David Marchant's PhD Thesis, The Open University, 2020. 186 pages",
  "doi": "10.21954/ou.ro.00011477",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study several aspects of the M\\\"{o}bius function, $\\mu[\\sigma,\\pi]$, on the poset of permutations under the pattern containment order. First, we consider cases where the lower bound of the poset is indecomposable. We show that $\\mu[\\sigma,\\pi]$ can be computed by considering just the indecomposable permutations contained in the upper bound. We apply this to the case where the upper bound is an increasing oscillation, and give a method for computing the value of the M\\\"{o}bius function that only involves evaluating simple inequalities. We then consider conditions on an interval which guarantee that the value of the M\\\"{o}bius function is zero. In particular, we show that if a permutation $\\pi$ contains two intervals of length 2, which are not order-isomorphic to one another, then $\\mu[1,\\pi] = 0$. This allows us to prove that the proportion of permutations of length $n$ with principal M\\\"{o}bius function equal to zero is asymptotically bounded below by $(1-1/e)^2 \\ge 0.3995$. This is the first result determining the value of $\\mu[1,\\pi]$ for an asymptotically positive proportion of permutations $\\pi$. Following this, we use ''2413-balloon'' permutations to show that the growth of the principal M\\\"{o}bius function on the permutation poset is exponential. This improves on previous work, which has shown that the growth is at least polynomial. We then generalise 2413-balloon permutations, and find a recursion for the value of the principal M\\\"{o}bius function of these generalisations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-26T18:47:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05"
    ],
    "keywords": [
      "pattern containment order",
      "möbius function",
      "upper bound",
      "permutation poset",
      "function equal"
    ],
    "tags": [
      "dissertation",
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 186,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}