On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
By Michael Henry Albert, M. Elder, A. Rechnitzer, P. Westcott, Mike Zabrocki. 2005
55 citations recorded by the source corpus.
We show that the Stanley-Wilf limit for the class of 4231-avoiding permutations is at least by 9.47. This bound shows that this class has the largest such limit among all classes of permutations avoiding a single permutation of length 4 and refutes the conjecture that the Stanley-Wilf limit of a class of permutations avoiding a single permutation of length k cannot exceed (k-1)^2. The result is established by constructing a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations and analysing their transition matrices.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/cf064a9dfe29b4c5c31b477ff9a44cad82e995e0
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Permutation classes (2014, methodology): “Using quite a bit of computation and the insertion encoding (introduced by Albert, Linton, and Ruškuc [15]), Albert, Elder, Rechnitzer, Westcott, and Zabrocki [13] showed that gr(Av(1324)) ≥ 9.47.”
- Generalized permutation patterns - a short survey (2008, background): “…Stanton [57] essentially studied the patterns 2 31, 2 13, 31 2, and 13 2 and their relation to a set of orthogonal polynomials generalizing the Laguerre polynomials, and one of these patterns also played a crucial role in the proof by Foata and Zeilberger [31] that Denert’s statistic is Mahonian.”