{
"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"
}
}
}