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). P146.
Preview |
PDF.
Filename: 1103.0173v1.pdf
Preprint Download (149kB)| 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.
ORCID iDs
Bernini, A., Ferrari, L. and Steingrimsson, E. ORCID: https://orcid.org/0000-0003-4611-0849;-
-
Item type: Article ID code: 33801 Dates: DateEvent2011PublishedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 19 Oct 2011 11:15 Last modified: 11 Nov 2024 09:51 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/33801