Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A probabilistic approach to consecutive pattern avoiding in permutations

Autor
Perarnau-Llobet, G.
Tipus d'activitat
Article en revista
Revista
Journal of combinatorial theory. Series A
Data de publicació
2013-07
Volum
120
Número
5
Pàgina inicial
998
Pàgina final
1011
DOI
https://doi.org/10.1016/j.jcta.2013.02.004 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0097316513000290 Obrir en finestra nova
Resum
We present a new approach to the problem of enumerating permutations of length n that avoid a fixed consecutive pattern of length m. We use this approach to give explicit upper and lower bounds on the number of permutations avoiding a consecutive pattern of length m. As a corollary, we obtain a simple proof of the CMP conjecture from Elizalde and Noy, regarding the most avoided pattern, recently proved by Elizalde. We also show that most of the patterns behave similarly to the least avoided one.
Paraules clau
CMP conjecture, Consecutive pattern avoiding, Monotone patterns, Permutations, Probabilistic method
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions

Participants

  • Perarnau Llobet, Guillem  (autor)