Picture of a black hole

Strathclyde Open Access research that creates ripples...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of research papers by University of Strathclyde researchers, including by Strathclyde physicists involved in observing gravitational waves and black hole mergers as part of the Laser Interferometer Gravitational-Wave Observatory (LIGO) - but also other internationally significant research from the Department of Physics. Discover why Strathclyde's physics research is making ripples...

Strathprints also exposes world leading research from the Faculties of Science, Engineering, Humanities & Social Sciences, and from the Strathclyde Business School.

Discover more...

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
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.