Avoidance of boxed mesh patterns on permutations

Avgustinovich, Sergey and Kitaev, Sergey and Valyuzhenich, Alexander (2013) Avoidance of boxed mesh patterns on permutations. Discrete Applied Mathematics, 161 (1-2). pp. 43-51. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2012.08.015)

Full text not available in this repository.Request a copy

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.

ORCID iDs

Avgustinovich, Sergey, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Valyuzhenich, Alexander;
CORE (COnnecting REpositories)