Automatic discovery of structural rules of permutation classes
From MaRDI portal
Publication:4629385
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.
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
Cites work
- scientific article; zbMATH DE number 5831716 (Why is no real title available?)
- scientific article; zbMATH DE number 1033192 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- A calculus for the random generation of labelled combinatorial structures
- An algorithm computing combinatorial specifications of 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
- Enumeration Schemes for Restricted Permutations
- Enumeration schemes and, more importantly, their automatic generation
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- Finding regular insertion encodings for permutation classes
- Finitely labeled generating trees and restricted permutations
- Generating trees and forbidden subsequences
- Geometric grid classes of permutations
- Grid classes and the Fibonacci dichotomy for restricted permutations
- On growth rates of closed permutation classes
- On the effective and automatic enumeration of polynomial permutation classes
- Permutation classes of polynomial growth
- Rationality for subclasses of 321-avoiding permutations
- Refining enumeration schemes to count according to permutation statistics
- Restricted permutations
- Restricted permutations
- Restricted permutations and the wreath product
- Simple permutations and pattern restricted permutations
- Small permutation classes
- The insertion encoding of permutations
- The number of Baxter permutations
- The shape of random pattern-avoiding permutations
- Wilf classification of subsets of eight and nine four-letter patterns
- Wilf classification of subsets of four letter patterns
Cited in
(6)- scientific article; zbMATH DE number 7559423 (Why is no real title available?)
- On the effective and automatic enumeration of polynomial permutation classes
- 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
Describes a project that uses
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)
