Automatic discovery of structural rules of permutation classes

Bean, Christian; Gudmundsson, Bjarki; Ulfarsson, Henning

doi:10.1090/mcom/3386

Automatic discovery of structural rules of permutation classes
HTML articles powered by AMS MathViewer

by Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson HTML | PDF

Math. Comp. 88 (2019), 1967-1990 Request permission

Abstract:

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.

References

M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), no. 1-3, 1–15. MR 2170110, DOI 10.1016/j.disc.2005.06.016
Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc, and Vincent Vatter, Geometric grid classes of permutations, Trans. Amer. Math. Soc. 365 (2013), no. 11, 5859–5881. MR 3091268, DOI 10.1090/S0002-9947-2013-05804-7
M. H. Albert, M. D. Atkinson, and Robert Brignall, Permutation classes of polynomial growth, Ann. Comb. 11 (2007), no. 3-4, 249–264. MR 2376105, DOI 10.1007/s00026-007-0318-x
M. H. Albert, R. Brignall, N. Ruškuc, and V. Vatter, Rationality for subclasses of 321-avoiding permutations, arXiv:1602.00672 (2016).
Michael H. Albert, Steve Linton, and Nik Ruškuc, The insertion encoding of permutations, Electron. J. Combin. 12 (2005), Research Paper 47, 31. MR 2176523
A. Arnarson, C. Bean, A. Bjarnason, U. Erlendsson, H. Ulfarsson, and S. Viktorsson, PermPAL, http://permpal.ru.is/, 2017.
M. D. Atkinson, Restricted permutations, Discrete Math. 195 (1999), no. 1-3, 27–38. MR 1663866, DOI 10.1016/S0012-365X(98)00162-9
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math. 259 (2002), no. 1-3, 19–36. MR 1948771, DOI 10.1016/S0012-365X(02)00443-0
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Carine Pivoteau, and Dominique Rossin, An algorithm computing combinatorial specifications of permutation classes, Discrete Appl. Math. 224 (2017), 16–44. MR 3637994, DOI 10.1016/j.dam.2017.02.013
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, and Dominique Rossin, Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial, Pure Math. Appl. (PU.M.A.) 21 (2010), no. 2, 119–135. MR 2810529
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, and Dominique Rossin, An algorithm for deciding the finiteness of the number of simple permutations in permutation classes, Adv. in Appl. Math. 64 (2015), 124–200. MR 3300331, DOI 10.1016/j.aam.2014.12.001
Andrew M. Baxter, Refining enumeration schemes to count according to permutation statistics, Electron. J. Combin. 21 (2014), no. 2, Paper 2.50, 27. MR 3244816
C. Bean, B. Gudmundsson, and H. Ulfarsson, PermStruct, https://github.com/PermutaTriangle/PermStruct, 2017.
A. Biere, Lingeling, Plingeling and Treengeling entering the SAT competition, 2013.
M.-L. Bruner, Central binomial coefficients also count (2431, 4231, 1432, 4132)-avoiders, (2015).
F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr., and M. Kleiman, The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978), no. 3, 382–394. MR 491652, DOI 10.1016/0097-3165(78)90068-7
Philippe Flajolet, Paul Zimmerman, and Bernard Van Cutsem, A calculus for the random generation of labelled combinatorial structures, Theoret. Comput. Sci. 132 (1994), no. 1-2, 1–35. MR 1290534, DOI 10.1016/0304-3975(94)90226-7
Gurobi Optimization, Inc., Gurobi optimizer reference manual, 2016.
Cheyne Homberger and Vincent Vatter, On the effective and automatic enumeration of polynomial permutation classes, J. Symbolic Comput. 76 (2016), 84–96. MR 3461260, DOI 10.1016/j.jsc.2015.11.019
Sophie Huczynska and Vincent Vatter, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13 (2006), no. 1, Research Paper 54, 14. MR 2240760
Tomá Kaiser and Martin Klazar, On growth rates of closed permutation classes, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 10, 20. Permutation patterns (Otago, 2003). MR 2028280
Donald E. Knuth, The art of computer programming. Vol. 3, Addison-Wesley, Reading, MA, 1998. Sorting and searching; Second edition [of MR0445948]. MR 3077154
William Kuszmaul, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Math. Comp. 87 (2018), no. 310, 987–1011. MR 3739226, DOI 10.1090/mcom/3216
Neal Madras and Hailong Liu, Random pattern-avoiding permutations, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 173–194. MR 2681860, DOI 10.1090/conm/520/10259
Toufik Mansour and Matthias Schork, Wilf classification of subsets of eight and nine four-letter patterns, J. Comb. Number Theory 8 (2016), no. 3, 257–283. MR 3701295
Toufik Mansour and Matthias Schork, Wilf classification of subsets of four letter patterns, J. Comb. Number Theory 8 (2016), no. 1, 1–129. MR 3585799
Sam Miner and Igor Pak, The shape of random pattern-avoiding permutations, Adv. in Appl. Math. 55 (2014), 86–130. MR 3176717, DOI 10.1016/j.aam.2013.12.004
Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), no. 4, 383–406. MR 829358, DOI 10.1016/S0195-6698(85)80052-4
N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.oeis.org, 2017.
Vincent Vatter, Finitely labeled generating trees and restricted permutations, J. Symbolic Comput. 41 (2006), no. 5, 559–572. MR 2209164, DOI 10.1016/j.jsc.2005.10.003
Vincent Vatter, Enumeration schemes for restricted permutations, Combin. Probab. Comput. 17 (2008), no. 1, 137–159. MR 2376427, DOI 10.1017/S0963548307008516
Vincent Vatter, Small permutation classes, Proc. Lond. Math. Soc. (3) 103 (2011), no. 5, 879–921. MR 2852292, DOI 10.1112/plms/pdr017
Vincent Vatter, Finding regular insertion encodings for permutation classes, J. Symbolic Comput. 47 (2012), no. 3, 259–265. MR 2869320, DOI 10.1016/j.jsc.2011.11.002
Julian West, Generating trees and forbidden subsequences, Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994), 1996, pp. 363–374 (English, with English and French summaries). MR 1417303, DOI 10.1016/S0012-365X(96)83023-8
Doron Zeilberger, Enumeration schemes and, more importantly, their automatic generation, Ann. Comb. 2 (1998), no. 2, 185–195. MR 1682929, DOI 10.1007/BF01608488