A structural characterisation of Av(1324) and new bounds on its growth rate

David Bevan, Robert Brignall, Andrew Elvey Price, Jay Pantone

Research output: Contribution to journalArticle

Abstract

We establish an improved lower bound of 10.271 for the exponential growth rate of the class of permutations avoiding the pattern 1324, and an improved upper bound of 13.5. These results depend on a new exact structural characterisation of 1324-avoiders as a subclass of an infinite staircase grid class, together with precise asymptotics of a small domino subclass whose enumeration we relate to West-two-stack-sortable permutations and planar maps. The bounds are established by carefully combining copies of the dominoes in particular ways consistent with the structural characterisation. The lower bound depends on concentration results concerning the substructure of a typical domino, the determination of exactly when dominoes can be combined in the fewest distinct ways, and technical analysis of the resulting generating function.
LanguageEnglish
JournalEuropean Journal of Combinatorics
Publication statusAccepted/In press - 17 Apr 2019

Fingerprint

Permutation
Lower bound
Technical Analysis
Planar Maps
Precise Asymptotics
Exponential Growth
Substructure
Enumeration
Generating Function
Upper bound
Grid
Distinct
Class

Keywords

  • permutation patterns
  • growth rate
  • asymptotic enumeration
  • Av(1324)

Cite this

@article{c751ac69dd2042df804389125555ac63,
title = "A structural characterisation of Av(1324) and new bounds on its growth rate",
abstract = "We establish an improved lower bound of 10.271 for the exponential growth rate of the class of permutations avoiding the pattern 1324, and an improved upper bound of 13.5. These results depend on a new exact structural characterisation of 1324-avoiders as a subclass of an infinite staircase grid class, together with precise asymptotics of a small domino subclass whose enumeration we relate to West-two-stack-sortable permutations and planar maps. The bounds are established by carefully combining copies of the dominoes in particular ways consistent with the structural characterisation. The lower bound depends on concentration results concerning the substructure of a typical domino, the determination of exactly when dominoes can be combined in the fewest distinct ways, and technical analysis of the resulting generating function.",
keywords = "permutation patterns, growth rate, asymptotic enumeration, Av(1324)",
author = "David Bevan and Robert Brignall and {Elvey Price}, Andrew and Jay Pantone",
year = "2019",
month = "4",
day = "17",
language = "English",
journal = "European Journal of Combinatorics",
issn = "0195-6698",

}

A structural characterisation of Av(1324) and new bounds on its growth rate. / Bevan, David; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay.

In: European Journal of Combinatorics, 17.04.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A structural characterisation of Av(1324) and new bounds on its growth rate

AU - Bevan, David

AU - Brignall, Robert

AU - Elvey Price, Andrew

AU - Pantone, Jay

PY - 2019/4/17

Y1 - 2019/4/17

N2 - We establish an improved lower bound of 10.271 for the exponential growth rate of the class of permutations avoiding the pattern 1324, and an improved upper bound of 13.5. These results depend on a new exact structural characterisation of 1324-avoiders as a subclass of an infinite staircase grid class, together with precise asymptotics of a small domino subclass whose enumeration we relate to West-two-stack-sortable permutations and planar maps. The bounds are established by carefully combining copies of the dominoes in particular ways consistent with the structural characterisation. The lower bound depends on concentration results concerning the substructure of a typical domino, the determination of exactly when dominoes can be combined in the fewest distinct ways, and technical analysis of the resulting generating function.

AB - We establish an improved lower bound of 10.271 for the exponential growth rate of the class of permutations avoiding the pattern 1324, and an improved upper bound of 13.5. These results depend on a new exact structural characterisation of 1324-avoiders as a subclass of an infinite staircase grid class, together with precise asymptotics of a small domino subclass whose enumeration we relate to West-two-stack-sortable permutations and planar maps. The bounds are established by carefully combining copies of the dominoes in particular ways consistent with the structural characterisation. The lower bound depends on concentration results concerning the substructure of a typical domino, the determination of exactly when dominoes can be combined in the fewest distinct ways, and technical analysis of the resulting generating function.

KW - permutation patterns

KW - growth rate

KW - asymptotic enumeration

KW - Av(1324)

UR - https://www.journals.elsevier.com/european-journal-of-combinatorics/

M3 - Article

JO - European Journal of Combinatorics

T2 - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -