Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

The Möbius function of the consecutive pattern poset

Bernini, A. and Ferrari, L. and Steingrimsson, E. (2011) The Möbius function of the consecutive pattern poset. The Electronic Journal of Combinatorics, 18 (1).

[img]
Preview
PDF - Draft Version
Download (146Kb) | Preview

    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.

    Item type: Article
    ID code: 33801
    Keywords: consecutive pattern poset , Möbius function , Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 19 Oct 2011 12:15
    Last modified: 05 Sep 2014 13:28
    URI: http://strathprints.strath.ac.uk/id/eprint/33801

    Actions (login required)

    View Item

    Fulltext Downloads: