Avoidance of boxed mesh patterns on permutations

Sergey Avgustinovich, Sergey Kitaev, Alexander Valyuzhenich

Research output: Contribution to journalArticle

11 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.
LanguageEnglish
Pages43-51
Number of pages9
JournalDiscrete Applied Mathematics
Volume161
Issue number1-2
Early online date7 Sep 2012
DOIs
Publication statusPublished - Jan 2013

Fingerprint

Permutation
Mesh
Catalan number
Enumeration
Analogue
Theorem

Keywords

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

Cite this

Avgustinovich, Sergey ; Kitaev, Sergey ; Valyuzhenich, Alexander. / Avoidance of boxed mesh patterns on permutations. In: Discrete Applied Mathematics. 2013 ; Vol. 161, No. 1-2. pp. 43-51.
@article{12490a9dc07b455a892a302c661b3a89,
title = "Avoidance of boxed mesh patterns on permutations",
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.",
keywords = "boxed mesh pattern, enumeration, Stanley–Wilf conjecture, Erdős–Szekeres theorem, generalized Catalan numbers",
author = "Sergey Avgustinovich and Sergey Kitaev and Alexander Valyuzhenich",
year = "2013",
month = "1",
doi = "10.1016/j.dam.2012.08.015",
language = "English",
volume = "161",
pages = "43--51",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
number = "1-2",

}

Avoidance of boxed mesh patterns on permutations. / Avgustinovich, Sergey; Kitaev, Sergey; Valyuzhenich, Alexander.

In: Discrete Applied Mathematics, Vol. 161, No. 1-2, 01.2013, p. 43-51.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Avoidance of boxed mesh patterns on permutations

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

AU - Valyuzhenich, Alexander

PY - 2013/1

Y1 - 2013/1

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

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

KW - boxed mesh pattern

KW - enumeration

KW - Stanley–Wilf conjecture

KW - Erdős–Szekeres theorem

KW - generalized Catalan numbers

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/mesh.pdf

U2 - 10.1016/j.dam.2012.08.015

DO - 10.1016/j.dam.2012.08.015

M3 - Article

VL - 161

SP - 43

EP - 51

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-2

ER -