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

Bevan, David and Brignall, Robert and Elvey Price, Andrew and Pantone, Jay (2020) A structural characterisation of Av(1324) and new bounds on its growth rate. European Journal of Combinatorics, 88. 103115. ISSN 0195-6698

[thumbnail of Bevan-etal-EJC-2019-A-structural-characterisation-of-Av1324-and-new-bounds-on-its-growth-rate]
Preview
 Text (Bevan-etal-EJC-2019-A-structural-characterisation-of-Av1324-and-new-bounds-on-its-growth-rate)
Bevan_etal_EJC_2019_A_structural_characterisation_of_Av1324_and_new_bounds_on_its_growth_rate.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (478kB)| Preview

    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.

    ORCID iDs

    Bevan, David ORCID logoORCID: https://orcid.org/0000-0001-7179-2285, Brignall, Robert, Elvey Price, Andrew and Pantone, Jay;
    • Item type:Article
      ID code:67764
      Dates:
      Date
      Event
      31 August 2020
      Published
      25 March 2020
      Published Online
      17 April 2019
      Accepted
      Keywords:permutation patterns, growth rate, asymptotic enumeration, Av(1324), Mathematics, Electronic computers. Computer science, Discrete Mathematics and Combinatorics, Computer Science(all)
      Subjects:Science > Mathematics
      Science > Mathematics > Electronic computers. Computer science
      Department:Faculty of Science > Computer and Information Sciences
      Depositing user: Pure Administrator
      Date deposited:13 May 2019 11:12
      Last modified:30 Apr 2021 00:37
      URI:https://strathprints.strath.ac.uk/id/eprint/67764
    CORE (COnnecting REpositories)