Decidability in geometric grid classes of permutations

Braunfeld, Samuel

doi:10.1090/proc/17083

Decidability in geometric grid classes of permutations
HTML articles powered by AMS MathViewer

by Samuel Braunfeld;

Proc. Amer. Math. Soc. 153 (2025), 987-1000

DOI: https://doi.org/10.1090/proc/17083

Published electronically: December 12, 2024

HTML | PDF | Request permission

Abstract:

We prove that the basis and the generating function of a geometric grid class of permutations $\mathrm {Geom}(M)$ are computable from the matrix $M$, as well as some variations on this result. Our main tool is monadic second-order logic on permutations and words.

References

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
Michael H. Albert, Nik Ruškuc, and Vincent Vatter, Inflations of geometric grid classes of permutations, Israel J. Math. 205 (2015), no. 1, 73–108. MR 3314583, DOI 10.1007/s11856-014-1098-8
Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté, Vadim V. Lozin, Vincent Vatter, and Victor Zamaraev, Letter graphs and geometric grid classes of permutations, SIAM J. Discrete Math. 36 (2022), no. 4, 2774–2797. MR 4508060, DOI 10.1137/21M1449646
Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin, and Viktor Zamaraev, Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions, arXiv:2402.12559 (2024).
Bogdan Alecu, Vadim Lozin, Dominique de Werra, and Viktor Zamaraev, Letter graphs and geometric grid classes of permutations: characterization and recognition, Discrete Appl. Math. 283 (2020), 482–494. MR 4114912, DOI 10.1016/j.dam.2020.01.038
Federico Ardila, Algebraic and geometric methods in enumerative combinatorics, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 3–172. MR 3409342
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
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz, On first-order transductions of classes of graphs, arXiv:2208.14412 (2022).
Robert Brignall and Vincent Vatter, Labelled well-quasi-order for permutation classes, Comb. Theory 2 (2022), no. 3, Paper No. 14, 54. MR 4498595, DOI 10.5070/c62359178
Kevin Cattell, Michael J. Dinneen, Rodney G. Downey, Michael R. Fellows, and Michael A. Langston, On computing graph minor obstruction sets, Theoret. Comput. Sci. 233 (2000), no. 1-2, 107–127. MR 1732180, DOI 10.1016/S0304-3975(97)00300-9
Volker Diekert, Combinatorics on traces, Lecture Notes in Computer Science, vol. 454, Springer-Verlag, Berlin, 1990. With a foreword by Wilfried Brauer. MR 1075995, DOI 10.1007/3-540-53031-2
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 Nik Ruškuc, Well quasi-order in combinatorics: embeddings and homomorphisms, Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 261–293. MR 3497273
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 286318
Jens Lagergren, An upper bound on the size of an obstruction, Graph structure theory (Seattle, WA, 1991) Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, 1993, pp. 601–621. MR 1224734, DOI 10.1090/conm/147/01202
Michal Opler, Structural and Algorithmic Properties of Permutation Classes, Ph.D. Thesis, Univerzita Karlova, Matematicko-fyzikální fakulta, Prauge, 2022.
Jay Pantone, The enumeration of permutations avoiding 3124 and 4312, Ann. Comb. 21 (2017), no. 2, 293–315. MR 3654900, DOI 10.1007/s00026-017-0352-2
Klaus Reinhardt, The complexity of translating logic to finite automata, Automata, logics, and infinite games, Lecture Notes in Comput. Sci., vol. 2500, Springer, Berlin, 2002, pp. 231–238. MR 2070744, DOI 10.1007/3-540-36387-4_{1}3
Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, Vol. 3, Springer, Berlin, 1997, pp. 389–455. MR 1470024
Szymon Toruńczyk, Lectures on Finite Model Theory, 2020. https://web.archive.org/web/20240814000337/https://duch.mimuw.edu.pl/~szymtor/fmt.pdf.
Vincent Vatter, Permutation classes, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 753–833. MR 3409353
Mark Weyer, Decidability of S1S and S2S, Automata, logics, and infinite games, Lecture Notes in Comput. Sci., vol. 2500, Springer, Berlin, 2002, pp. 207–230. MR 2070743, DOI 10.1007/3-540-36387-4_{1}2