Automatic discovery of structural rules of permutation classes
From MaRDI portal
Publication:4629385
DOI10.1090/MCOM/3386zbMATH Open1407.05004arXiv1705.04109OpenAlexW2963548301WikidataQ129219237 ScholiaQ129219237MaRDI QIDQ4629385FDOQ4629385
Authors: Christian Bean, Bjarki Agust Gudmundsson, Henning Úlfarsson 
Publication date: 22 March 2019
Published in: Mathematics of Computation (Search for Journal in Brave)
Abstract: We introduce an algorithm that conjectures the structure of a permutation class in the form of a disjoint cover of "rules"; similar to generalized grid classes. The cover is usually easily verified by a human and translated into an enumeration. The algorithm is successful on different inputs than other algorithms and can succeed with 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 can sometimes allow an enumeration of the permutation class with respect to permutation statistics, as well as choosing a permutation uniformly at random from the permutation class. We sketch a new algorithm formalizing the human verification of the conjectured covers.
Full work available at URL: https://arxiv.org/abs/1705.04109
Recommendations
- On the effective and automatic enumeration of polynomial permutation classes
- Combinatorial specification of permutation classes
- An algorithm computing combinatorial specifications of permutation classes
- Permutation classes of polynomial growth
- Finding regular insertion encodings for permutation classes
Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)
Cites Work
- Title not available (Why is that?)
- Finding regular insertion encodings for permutation classes
- Enumeration schemes and, more importantly, their automatic generation
- Restricted permutations
- Title not available (Why is that?)
- Finitely labeled generating trees and restricted permutations
- The number of Baxter permutations
- Enumeration Schemes for Restricted Permutations
- A calculus for the random generation of labelled combinatorial structures
- Generating trees and forbidden subsequences
- Restricted permutations and the wreath product
- Restricted permutations
- Simple permutations and pattern restricted permutations
- Title not available (Why is that?)
- The shape of random pattern-avoiding permutations
- The insertion encoding of permutations
- Refining enumeration schemes to count according to permutation statistics
- On growth rates of closed permutation classes
- Grid classes and the Fibonacci dichotomy for restricted permutations
- Geometric grid classes of permutations
- Small permutation classes
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial
- An algorithm computing combinatorial specifications of permutation classes
- Permutation classes of polynomial growth
- On the effective and automatic enumeration of polynomial permutation classes
- Wilf classification of subsets of four letter patterns
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- Wilf classification of subsets of eight and nine four-letter patterns
- Rationality for subclasses of 321-avoiding permutations
Cited In (6)
- On the effective and automatic enumeration of polynomial permutation classes
- Title not available (Why is that?)
- Finding regular insertion encodings for permutation classes
- Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes
- On permutation patterns with constrained gap sizes
- An algorithm computing combinatorial specifications of permutation classes
Uses Software
This page was built for publication: Automatic discovery of structural rules of permutation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629385)
