On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia | NOVA. The University of Newcastle's Digital Repository

Home

Description	Size	Format
Author final version	119 KB	Adobe Acrobat PDF	View/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/928094

Title: On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
Author/Creator: Albert, M. H.; Elder, Murray; Rechnitzer, A.; Westcott, P.; Zabrocki, M.
Description: 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.
Relation: Advances in Applied Mathematics Vol. 36, Issue 2, p. 96-105
Publisher Link: http://dx.doi.org/10.1016/j.aam.2005.05.007
Date: 2006
Publisher: Academic Press
Keyword(s): permutation classes; Automata
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/928094
Identifier: ISSN:0196-8858
Language: eng

16 Visitors

32 Hits

NOVA. The University of Newcastle's Digital Repository