A formula for the Möbius function of the permutation poset based on a topological decomposition

Smith, JP ORCID logoORCID: https://orcid.org/0000-0002-4209-1604, 2017. A formula for the Möbius function of the permutation poset based on a topological decomposition. Advances in Applied Mathematics, 91, pp. 98-114. ISSN 0196-8858

[thumbnail of 1390800_a2014_Smith.pdf]
Preview
Text
1390800_a2014_Smith.pdf - Post-print

Download (353kB) | Preview

Abstract

We present a two term formula for the Möbius function of intervals in the poset of all permutations, ordered by pattern containment. The first term in this formula is the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. We also present a result on the Möbius function of posets connected by a poset fibration.

Item Type: Journal article
Publication Title: Advances in Applied Mathematics
Creators: Smith, J.P.
Publisher: Elsevier
Date: October 2017
Volume: 91
ISSN: 0196-8858
Identifiers:
Number
Type
10.1016/j.aam.2017.06.002
DOI
S019688581730091X
Publisher Item Identifier
1390800
Other
Divisions: Schools > School of Science and Technology
Record created by: Linda Sullivan
Date Added: 21 Apr 2021 08:33
Last Modified: 17 Jan 2022 13:54
URI: https://irep.ntu.ac.uk/id/eprint/42727

Actions (login required)

Edit View Edit View

Statistics

Views

Views per month over past year

Downloads

Downloads per month over past year