On the Möbius function of permutations with one descent

MaRDI QIDQ405198zbMATH OpenFDO

Authors Jason P. Smith

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5926, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Möbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Multiplicative number theory (11N99)

Abstract: The set of all permutations, ordered by pattern containment, is a poset. We give a formula for the M"obius function of intervals $[1,pi]$ in this poset, for any permutation $pi$ with at most one descent. We compute the M"obius function as a function of the number and positions of pairs of consecutive letters in $pi$ that are consecutive in value. As a result of this we show that the M"obius function is unbounded on the poset of all permutations. We show that the M"obius function is zero on any interval $[1,pi]$ where $pi$ has a triple of consecutive letters whose values are consecutive and monotone. We also conjecture values of the M"obius function on some other intervals of permutations with at most one descent.

Recommendations

• The Möbius function of the permutation pattern poset
• The Möbius function of the consecutive pattern poset
• 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
• Intervals of permutations with a fixed number of descents are shellable

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• On the enumeration of \(d\)-minimal permutations
• Some open problems on permutation patterns
• The Möbius function of a composition poset
• The Möbius function of separable and decomposable permutations
• The Möbius function of the permutation pattern poset

Cited in

(15)

• A formula for the Möbius function of the permutation poset based on a topological decomposition
• The Möbius function of the permutation pattern poset
• Zeros of the Möbius function of permutations
• One-way permutations on elliptic curves
• scientific article; zbMATH DE number 6806830 (Why is no real title available?)
• Pattern posets
• On the topology of the permutation pattern poset
• Intervals of permutations with a fixed number of descents are shellable
• Vincular pattern posets and the Möbius function of the quasi-consecutive pattern poset
• On the Möbius function and topology of general pattern posets
• On the growth of the Möbius function of permutations
• The Möbius function of permutations with an indecomposable lower bound
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• 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

This page was built for publication: On the Möbius function of permutations with one descent

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