<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Permutation Classes of Polynomial Growth
M.H. Albert1, M.D. Atkinson1, and Robert Brignall2
1Department of Computer Science, University of Otago, PO Box 56, Dunedin, New Zealand
{malbert, mike}@cs.otago.ac.nz
2Department of Mathematics and Statistics, University of St Andrews, St Andrews, Fife KY16 9AG, Scotland
Annals of Combinatorics 11 (3-4) p.249-264 September, 2007
AMS Subject Classification: 05A15, 05A05
A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue of all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials.
Keywords: restricted permutations, pattern avoidance, growth rate, polynomial growth


1. M.H. Albert, M.D. Atkinson, and N. Ruškuc, Regular closed sets of permutations, Theoret. Comput. Sci. 306 (1-3) (2003) 85-100.

2. M.D. Atkinson, Restricted permutations, Discrete Math. 195 (1-3) (1999) 27-38.

3. M.D. Atkinson, M.M. Murphy, and N. Ruskuc, Partially well-ordered closed sets of permutations, Order 19 (2) (2002) 101-113.

4. M.D. Atkinson, M.M. Murphy, and N. Ruškuc, Pattern avoidance classes and subpermutations, Electron. J. Combin. 12 (2005) #R60.

5. M.D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math. 259 (1-3) (2002) 19-36.

6. S. Huczynska and V. Vatter, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13 (2006) #R54.

7. T. Kaiser and M. Klazar, On growth rates of closed permutation classes, Electron. J. Combin. 9 (2) (2002-2003) #R10.

8. A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (1) (2004) 153-160.

9. T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 26 (3) (2001) 258-269.

10. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383- 406.

11. J.West, Generating trees and forbidden subsequences, Discrete Math. 157 (1-3) (1996) 363- 374.