Picture of neon light reading 'Open'

Discover open research at Strathprints as part of International Open Access Week!

23-29 October 2017 is International Open Access Week. The Strathprints institutional repository is a digital archive of Open Access research outputs, all produced by University of Strathclyde researchers.

Explore recent world leading Open Access research content this Open Access Week from across Strathclyde's many research active faculties: Engineering, Science, Humanities, Arts & Social Sciences and Strathclyde Business School.

Explore all Strathclyde Open Access research outputs...

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

Smith, Jason P. (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

[img] Text (Smith-AAM-2017-formula-for-the-mobius-function-of-the-permutation-poset-based-on-a-topological-decomposition)
Smith_AAM_2017_formula_for_the_mobius_function_of_the_permutation_poset_based_on_a_topological_decomposition.pdf - Accepted Author Manuscript
Restricted to Repository staff only until 3 July 2018.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (194kB) | Request a copy from the Strathclyde author


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.