Avoidance of boxed mesh patterns on permutations

Sergey Avgustinovich, Sergey Kitaev, Alexander Valyuzhenich

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

We introduce the notion of a boxed mesh pattern and study avoidance of these patterns on permutations. We prove that the celebrated former Stanley–Wilf conjecture is not true for all but eleven boxed mesh patterns; for seven out of the eleven patterns the former conjecture is true, while we do not know the answer for the remaining four (length-four) patterns. Moreover, we prove that an analogue of a well-known theorem of Erdős and Szekeres does not hold for boxed mesh patterns of lengths larger than 2. Finally, we discuss enumeration of permutations avoiding simultaneously two or more length-three boxed mesh patterns, where we meet generalized Catalan numbers.
Original languageEnglish
Pages (from-to)43-51
Number of pages9
JournalDiscrete Applied Mathematics
Volume161
Issue number1-2
Early online date7 Sep 2012
DOIs
Publication statusPublished - Jan 2013

Keywords

  • boxed mesh pattern
  • enumeration
  • Stanley–Wilf conjecture
  • Erdős–Szekeres theorem
  • generalized Catalan numbers

Fingerprint Dive into the research topics of 'Avoidance of boxed mesh patterns on permutations'. Together they form a unique fingerprint.

  • Cite this