On the growth of the Möbius function of permutations

DOI10.1016/J.JCTA.2019.105121zbMATH Open1428.05010OpenAlexW2891151120MaRDI QIDQ2010617FDOQ2010617

Authors Vít Jelínek, Ida Kantor, Jan Kynčl, Martin Tancer

Publication date 27 November 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.05774

zbMATH Keywords

permutation posetpermutation embeddingMöbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

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 $p{i}_n$ of size $2n-2$ for which $mu(1,p{i}_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 $$ in terms of the number of embeddings of the elements of the interval into $$.

Recommendations

• 2413-balloon permutations and the growth of the Möbius function
• The Möbius function of the permutation pattern poset
• The Möbius function of permutations with an indecomposable lower bound
• On the Möbius function of permutations with one descent
• Zeros of the Möbius function of permutations

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• 2413-balloon permutations and the growth of the Möbius function
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• Chains in the lattice of noncrossing partitions
• Intervals of permutations with a fixed number of descents are shellable
• On the Möbius function of permutations with one descent
• On the poset of partitions of an integer
• On the topology of the permutation pattern poset
• Pattern matching for permutations
• Poset topology: tools and applications
• Posets with maximal Möbius function
• The Möbius function of a composition poset
• The Möbius function of a restricted composition poset.
• The Möbius function of factor order
• The Möbius function of generalized subword order
• The Möbius function of partitions with restricted block sizes
• The Möbius function of permutations with an indecomposable lower bound
• The Möbius function of separable and decomposable permutations
• The Möbius function of the permutation pattern poset
• The On-Line Encyclopedia of Integer Sequences
• The patterns of permutations

Cited in

(4)

• Zeros of the Möbius function of permutations
• scientific article; zbMATH DE number 6806830 (Why is no real title available?)
• Tangent-Chebyshev maps over finite fields: new properties and functional graphs
• 2413-balloon permutations and the growth of the Möbius function

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the growth of the Möbius function of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010617)