On avoidance of V- and ^-patterns in permutations

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

Abstract

We study V- and ^-patterns which generalize valleys and peaks, as well as increasing and decreasing runs, in permutations. A complete classi¯cation of permutations (multi)-avoiding V- and ¤-patterns of length 4 is given. We also establish a connection between restricted permutations and matchings in the coronas of complete graphs.
Original languageEnglish
Pages (from-to)203-215
Number of pages13
JournalArs Combinatoria
Volume97
Publication statusPublished - Oct 2010

    Fingerprint

Keywords

  • pattern avoidance
  • pattern avoiding permutation
  • valleys
  • peaks
  • partially ordered patterns
  • corona of a complete graph

Cite this