<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
On Permutation Pattern Classes with Two Restrictions Only
M.D. Atkinson
Department of Computer Science, University of Otago, P.O. Box 56, Dunedin 9054, New Zealand
mike@cs.otago.ac.nz
Annals of Combinatorics 11 (3-4) p.271-283 September, 2007
AMS Subject Classification: 05A05, 05A15
Abstract:
Permutation pattern classes that are defined by avoiding two permutations only and which contain only finitely many simple permutations are characterized and their growth rates are determined.
Keywords: permutation, pattern, growth rate

References:

1. M.H. Albert and M.D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (1-3) (2005) 1-15.

2. M.H. Albert, M.D. Atkinson, and R. Brignall, Permutation classes of polynomial growth, Ann. Combin., to appear.

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

4. R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin. 6 (1999) #N1.

5. P. Bose, J.F. Buss, and A. Lubiw, Pattern matching for permutations, Inform. Process. Lett. 65 (5) (1998) 277-283.

6. R. Brignall, N. Ruškuc, and V. Vatter, Simple permutations: decidability and unavoidable substructures, arXiv:math.CO/0609211.

7. P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935) 463–470.

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.