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

Jason P. Smith

Research output: Working paper

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 new result on the Möbius function of posets connected by a poset fibration related to a result of Björner, Wachs and Welker.
Original languageEnglish
Pages17
Publication statusPublished - 14 Jun 2015

Fingerprint

Poset
Permutation
Decomposition
Decompose
Term
Vanish
Interval
Polynomials
Fibration
Proportion
Polynomial
Computing
Zero

Keywords

  • Möbius function
  • posets
  • permutations
  • pattern containment
  • combinatorics

Cite this

@techreport{8d8ff607ff9d4d4eba2eb77274e24220,
title = "A formula for the M{\"o}bius function of the permutation poset based on a topological decomposition",
abstract = "We present a two term formula for the M{\"o}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{\"o}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{\"o}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 new result on the M{\"o}bius function of posets connected by a poset fibration related to a result of Bj{\"o}rner, Wachs and Welker.",
keywords = "M{\"o}bius function, posets, permutations, pattern containment, combinatorics",
author = "Smith, {Jason P.}",
year = "2015",
month = "6",
day = "14",
language = "English",
pages = "17",
type = "WorkingPaper",

}

TY - UNPB

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

AU - Smith, Jason P.

PY - 2015/6/14

Y1 - 2015/6/14

N2 - 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 new result on the Möbius function of posets connected by a poset fibration related to a result of Björner, Wachs and Welker.

AB - 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 new result on the Möbius function of posets connected by a poset fibration related to a result of Björner, Wachs and Welker.

KW - Möbius function

KW - posets

KW - permutations

KW - pattern containment

KW - combinatorics

UR - http://arxiv.org/abs/1506.04406

M3 - Working paper

SP - 17

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

ER -