On the growth of the Möbius function of permutations

DOI10.1016/J.JCTA.2019.105121zbMATH Open1428.05010arXiv1809.05774OpenAlexW2891151120MaRDI 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)

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 $$.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• 2413-balloon permutations and the growth of the Möbius function
• Tangent-Chebyshev maps over finite fields: new properties and functional graphs
• Zeros of the Möbius function of permutations

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)