×

Automatic discovery of structural rules of permutation classes. (English) Zbl 1407.05004

Summary: We introduce an algorithm that produces conjectures regarding the structure of permutation classes. These conjectures take the form of a disjoint cover of “rules”, each of which is similar to a generalized grid class. Such a cover is usually easily verified by a human and can often be translated directly into an enumeration. The algorithm is successful in many cases where other algorithms fail and is theoretically guaranteed to succeed on any polynomial permutation class. We apply it to every non-polynomial permutation class avoiding a set of length four patterns. The structures found by the algorithm sometimes allow one to enumerate a permutation class with respect to permutation statistics, and often yield a method for sampling uniformly at random from the class. We additionally sketch a second algorithm formalizing the human verification of the conjectured covers.

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albert, M. H.; Atkinson, M. D., Simple permutations and pattern restricted permutations, Discrete Math., 300, 1-3, 1-15 (2005) · Zbl 1073.05002 · doi:10.1016/j.disc.2005.06.016
[2] Albert, Michael H.; Atkinson, M. D.; Bouvel, Mathilde; Ru\v{s}kuc, Nik; Vatter, Vincent, Geometric grid classes of permutations, Trans. Amer. Math. Soc., 365, 11, 5859-5881 (2013) · Zbl 1271.05004 · doi:10.1090/S0002-9947-2013-05804-7
[3] Albert, M. H.; Atkinson, M. D.; Brignall, Robert, Permutation classes of polynomial growth, Ann. Comb., 11, 3-4, 249-264 (2007) · Zbl 1141.05009 · doi:10.1007/s00026-007-0318-x
[4] rational321 M. H. Albert, R. Brignall, N. Ruskuc, and V. Vatter, Rationality for subclasses of 321-avoiding permutations, arXiv:1602.00672 (2016). · Zbl 1414.05004
[5] Albert, Michael H.; Linton, Steve; Ru\v{s}kuc, Nik, The insertion encoding of permutations, Electron. J. Combin., 12, Research Paper 47, 31 pp. (2005) · Zbl 1081.05001
[6] permpal A. Arnarson, C. Bean, A. Bjarnason, U. Erlendsson, H. Ulfarsson, and S. Viktorsson, PermPAL, http://permpal.ru.is/, 2017.
[7] Atkinson, M. D., Restricted permutations, Discrete Math., 195, 1-3, 27-38 (1999) · Zbl 0932.05002 · doi:10.1016/S0012-365X(98)00162-9
[8] Atkinson, M. D.; Stitt, T., Restricted permutations and the wreath product, Discrete Math., 259, 1-3, 19-36 (2002) · Zbl 1013.05004 · doi:10.1016/S0012-365X(02)00443-0
[9] Bassino, Fr\'{e}d\'{e}rique; Bouvel, Mathilde; Pierrot, Adeline; Pivoteau, Carine; Rossin, Dominique, An algorithm computing combinatorial specifications of permutation classes, Discrete Appl. Math., 224, 16-44 (2017) · Zbl 1361.05004 · doi:10.1016/j.dam.2017.02.013
[10] Bassino, Fr\'{e}d\'{e}rique; Bouvel, Mathilde; Pierrot, Adeline; Rossin, Dominique, Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial, Pure Math. Appl. (PU.M.A.), 21, 2, 119-135 (2010) · Zbl 1265.05007
[11] Bassino, Fr\'{e}d\'{e}rique; Bouvel, Mathilde; Pierrot, Adeline; Rossin, Dominique, An algorithm for deciding the finiteness of the number of simple permutations in permutation classes, Adv. in Appl. Math., 64, 124-200 (2015) · Zbl 1306.05003 · doi:10.1016/j.aam.2014.12.001
[12] Baxter, Andrew M., Refining enumeration schemes to count according to permutation statistics, Electron. J. Combin., 21, 2, Paper 2.50, 27 pp. (2014) · Zbl 1300.05026
[13] structrepo C. Bean, B. Gudmundsson, and H. Ulfarsson, PermStruct, https://github.com/PermutaTriangle/PermStruct, 2017.
[14] lingeling A. Biere, Lingeling, Plingeling and Treengeling entering the SAT competition, 2013.
[15] Bruner M.-L. Bruner, Central binomial coefficients also count (2431, 4231, 1432, 4132)-avoiders, (2015).
[16] Chung, F. R. K.; Graham, R. L.; Hoggatt, V. E., Jr.; Kleiman, M., The number of Baxter permutations, J. Combin. Theory Ser. A, 24, 3, 382-394 (1978) · Zbl 0398.05003 · doi:10.1016/0097-3165(78)90068-7
[17] Flajolet, Philippe; Zimmerman, Paul; Van Cutsem, Bernard, A calculus for the random generation of labelled combinatorial structures, Theoret. Comput. Sci., 132, 1-2, 1-35 (1994) · Zbl 0799.68143 · doi:10.1016/0304-3975(94)90226-7
[18] gurobi Gurobi Optimization, Inc., Gurobi optimizer reference manual, 2016.
[19] Homberger, Cheyne; Vatter, Vincent, On the effective and automatic enumeration of polynomial permutation classes, J. Symbolic Comput., 76, 84-96 (2016) · Zbl 1331.05016 · doi:10.1016/j.jsc.2015.11.019
[20] Huczynska, Sophie; Vatter, Vincent, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin., 13, 1, Research Paper 54, 14 pp. (2006) · Zbl 1098.05003
[21] Kaiser, Tom\'{a}\v{s}; Klazar, Martin, On growth rates of closed permutation classes, Electron. J. Combin., 9, 2, Research paper 10, 20 pp. (2002/03) · Zbl 1015.05002
[22] Knuth, Donald E., The Art of Computer Programming. Vol. 3, xiv+780 pp. (1998), Addison-Wesley, Reading, MA · Zbl 0895.68054
[23] Kuszmaul, William, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Math. Comp., 87, 310, 987-1011 (2018) · Zbl 1377.05004 · doi:10.1090/mcom/3216
[24] Madras, Neal; Liu, Hailong, Random pattern-avoiding permutations. Algorithmic Probability and Combinatorics, Contemp. Math. 520, 173-194 (2010), Amer. Math. Soc., Providence, RI · Zbl 1209.05005 · doi:10.1090/conm/520/10259
[25] Mansour, Toufik; Schork, Matthias, Wilf classification of subsets of eight and nine four-letter patterns, J. Comb. Number Theory, 8, 3, 257-283 (2016) · Zbl 1377.05010
[26] Mansour, Toufik; Schork, Matthias, Wilf classification of subsets of four letter patterns, J. Comb. Number Theory, 8, 1, 1-129 (2016) · Zbl 1358.05016
[27] Miner, Sam; Pak, Igor, The shape of random pattern-avoiding permutations, Adv. in Appl. Math., 55, 86-130 (2014) · Zbl 1300.05032 · doi:10.1016/j.aam.2013.12.004
[28] Simion, Rodica; Schmidt, Frank W., Restricted permutations, European J. Combin., 6, 4, 383-406 (1985) · Zbl 0615.05002 · doi:10.1016/S0195-6698(85)80052-4
[29] OEIS N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.oeis.org, 2017. · Zbl 1044.11108
[30] Vatter, Vincent, Finitely labeled generating trees and restricted permutations, J. Symbolic Comput., 41, 5, 559-572 (2006) · Zbl 1124.05004 · doi:10.1016/j.jsc.2005.10.003
[31] Vatter, Vincent, Enumeration schemes for restricted permutations, Combin. Probab. Comput., 17, 1, 137-159 (2008) · Zbl 1133.05004 · doi:10.1017/S0963548307008516
[32] Vatter, Vincent, Small permutation classes, Proc. Lond. Math. Soc. (3), 103, 5, 879-921 (2011) · Zbl 1258.05004 · doi:10.1112/plms/pdr017
[33] Vatter, Vincent, Finding regular insertion encodings for permutation classes, J. Symbolic Comput., 47, 3, 259-265 (2012) · Zbl 1237.05014 · doi:10.1016/j.jsc.2011.11.002
[34] West, Julian, Generating trees and forbidden subsequences, Discrete Math.. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994), 157, 1-3, 363-374 (1996) · Zbl 0877.05002 · doi:10.1016/S0012-365X(96)83023-8
[35] Zeilberger, Doron, Enumeration schemes and, more importantly, their automatic generation, Ann. Comb., 2, 2, 185-195 (1998) · Zbl 0931.05006 · doi:10.1007/BF01608488
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.