### Abstract

Language | English |
---|---|

Pages | 43-51 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 161 |

Issue number | 1-2 |

Early online date | 7 Sep 2012 |

DOIs | |

Publication status | Published - Jan 2013 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*,

*161*(1-2), 43-51. https://doi.org/10.1016/j.dam.2012.08.015

}

*Discrete Applied Mathematics*, vol. 161, no. 1-2, pp. 43-51. https://doi.org/10.1016/j.dam.2012.08.015

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

Research output: Contribution to journal › Article

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 -