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.

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Item metadata

  Item type:	Article
  ID code:	33801
  Dates:	Date Event 2011 Published
  Subjects:	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:	08 Apr 2024 19:26
  Related URLs:	Journal or Publication Journal or Publication
  URI:	https://strathprints.strath.ac.uk/id/eprint/33801