DocServer

On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia

Albert, M.H. and Elder, Murray and Rechnitzer, A. and Westcott, P. and Zabrocki, M. (2006) On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia. Advances in Applied Mathematics, 36 (2). pp. 96-105.

Full text not available from this repository.

Abstract

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.

Item Type: Article
Uncontrolled Keywords: permutation classes, Automata
Subjects: UNSPECIFIED
Faculty: UNSPECIFIED
Depositing User: Dr David Allingham
Date Deposited: 28 Sep 2012 12:05
Last Modified: 12 Jun 2013 12:58
URI: https://docserver.carma.newcastle.edu.au/id/eprint/1163

Actions (login required)

View Item