The Möbius function of the consecutive pattern poset

A. Bernini, L. Ferrari, E. Steingrimsson

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

An occurrence of a consecutive permutation pattern p in a permutation π is a segment of consecutive letters of π whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the Möbius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.
LanguageEnglish
Article numberP146
Number of pages12
JournalThe Electronic Journal of Combinatorics
Volume18
Issue number1
Publication statusPublished - 2011

Fingerprint

Möbius Function
Poset
Consecutive
Permutation
Interval
Polynomial-time Algorithm
Polynomials

Keywords

  • consecutive pattern poset
  • Möbius function

Cite this

@article{3c4fbcdaf5ac4fefb41c56c43022619b,
title = "The M{\"o}bius function of the consecutive pattern poset",
abstract = "An occurrence of a consecutive permutation pattern p in a permutation π is a segment of consecutive letters of π whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the M{\"o}bius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the M{\"o}bius function. In particular, we show that the M{\"o}bius function only takes the values −1, 0 and 1.",
keywords = "consecutive pattern poset , M{\"o}bius function",
author = "A. Bernini and L. Ferrari and E. Steingrimsson",
year = "2011",
language = "English",
volume = "18",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "1",

}

The Möbius function of the consecutive pattern poset. / Bernini, A.; Ferrari, L.; Steingrimsson, E.

In: The Electronic Journal of Combinatorics, Vol. 18, No. 1, P146, 2011.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Möbius function of the consecutive pattern poset

AU - Bernini, A.

AU - Ferrari, L.

AU - Steingrimsson, E.

PY - 2011

Y1 - 2011

N2 - An occurrence of a consecutive permutation pattern p in a permutation π is a segment of consecutive letters of π whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the Möbius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.

AB - An occurrence of a consecutive permutation pattern p in a permutation π is a segment of consecutive letters of π whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the Möbius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.

KW - consecutive pattern poset

KW - Möbius function

UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p146/pdf

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

M3 - Article

VL - 18

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 1

M1 - P146

ER -