×

On the growth of merges and staircases of permutation classes. (English) Zbl 1418.05015

Summary: There is a well-known upper bound due to A. Claesson et al. [J. Comb. Theory, Ser. A 119, No. 8, 1680–1691 (2012; Zbl 1246.05002)] for the growth rate of the merge of two permutation classes. Curiously, there is no known merge for which this bound is not achieved. Using linear algebraic techniques and appealing to the theory of Toeplitz matrices, we provide sufficient conditions for the growth rate to equal this upper bound. In particular, our results apply to all merges of principal permutation classes. We end by demonstrating how our techniques relate to the results of M. Bóna [J. Comb. Theory, Ser. A 110, No. 2, 223–235 (2005; Zbl 1067.05003), Eur. J. Comb. 28, No. 1, 75–85 (2007; Zbl 1105.05002)].

MSC:

05A16 Asymptotic enumeration
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] M.H. Albert, On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation, Random Struct. Algor. 31 (2007), 227-238. · Zbl 1129.05002 · doi:10.1002/rsa.20140
[2] M.H. Albert, S. Linton and N. Ruškuc, The insertion encoding of permutations, Electr. J. Combin. 12 (2005), paper 47, 31 pp. · Zbl 1081.05001
[3] M.H. Albert and V. Vatter, An elementary proof of Bevan’s theorem on the growth of grid classes of permutations, arXiv 1608.06967, to appear in Proc. Edinburgh Math. Soc. · Zbl 1422.05001
[4] R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electr. J. Combin. 6 (1999), note 1, 4 pp. · Zbl 0922.05002
[5] M.D. Atkinson, Restricted permutations, Discr. Math. 195 (1999), 27-38. · Zbl 0932.05002
[6] D. Bevan, Growth rates of permutation grid classes, tours on graphs, and the spectral radius, Trans. Amer. Math. Soc. 367 (2015), 5863-5889. · Zbl 1311.05003 · doi:10.1090/S0002-9947-2015-06280-1
[7] D. Bevan, R. Brignall, A. Elvey Price and J. Pantone, A structural characterisation of \({\rm Av}(1324)\) and new bounds on its growth rate, Electr. Notes Discr. Math. 61 (2017), 123-129. · Zbl 1378.05002
[8] M. Bóna, Exact enumeration of \(1342\)-avoiding permutations: A close link with labeled trees and planar maps, J. Combin. Th. Ser. A 80 (1997), 257-272. · Zbl 0887.05004
[9] —-, The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns, J. Combin. Th. Ser. A 110 (2005), 223-235. · Zbl 1067.05003
[10] —-, New records in Stanley-Wilf limits, European J. Combin. 28 (2007), 75-85. · Zbl 1105.05002
[11] —-, A new upper bound for \(1324\)-avoiding permutations, Combin. Prob. Comp. 23 (2014), 717-724. · Zbl 1298.05019
[12] —-, A new record for \(1324\)-avoiding permutations, European J. Math. 1 (2015), 198-206. · Zbl 1310.05007
[13] A. Claesson, V. Jelí nek and E. Steingrí msson, Upper bounds for the Stanley-Wilf limit of \(1324\) and other layered patterns, J. Combin. Th. Ser. A 119 (2012), 1680-1691. · Zbl 1246.05002
[14] V. Jelí nek and P. Valtr, Splittings and Ramsey properties of permutation classes, Adv. Appl. Math. 63 (2015), 41-67. · Zbl 1304.05146
[15] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Th. Ser. A 107 (2004), 153-160. · Zbl 1051.05004 · doi:10.1016/j.jcta.2004.04.002
[16] C. Meyer, Matrix analysis and applied linear algebra, SIAM, Philadelphia, PA, 2000. · Zbl 0962.15001
[17] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981), 115-136. · Zbl 0509.20009 · doi:10.1016/0001-8708(81)90012-8
[18] Z. Stankova, Forbidden subsequences, Discr. Math. 132 (1994), 291-316. · Zbl 0810.05011 · doi:10.1016/0012-365X(94)90242-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.