A Structural Characterisation of Av(1324) and New Bounds On Its Growth Rate

Authors

David Bevan, University of Strathclyde
Robert Brignall, The Open University
Andrew Elvey Price, Université de Bordeaux
Jay Pantone, Marquette UniversityFollow

Document Type

Article

Language

eng

Publication Date

8-2020

Publisher

Elsevier

Source Publication

European Journal of Combinatorics

Source ISSN

0195-6698

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.

Comments

Accepted version. European Journal of Combinatorics, Vol. 88 (August 2020): 103115. DOI. © 2020 Elsevier. Used with permission.

Recommended Citation

Bevan, David; Brignall, Robert; Price, Andrew Elvey; and Pantone, Jay, "A Structural Characterisation of Av(1324) and New Bounds On Its Growth Rate" (2020). Mathematical and Statistical Science Faculty Research and Publications. 37.
https://epublications.marquette.edu/math_fac/37