tailieunhanh - Báo cáo toán học: "Grid classes and the Fibonacci dichotomy for restricted permutations"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Grid classes and the Fibonacci dichotomy for restricted permutations. | Grid classes and the Fibonacci dichotomy for restricted permutations Sophie Huczynska and Vincent Vatted School of Mathematics and Statistics University of St Andrews St Andrews Fife Scotland sophieh vince @ http tsophieh vince Submitted Feb 9 2006 Accepted Jun 5 2006 Published Jun 23 2006 Mathematics Subject Classification 05A05 05A15 05A16 Abstract We introduce and characterise grid classes which are natural generalisations of other well-studied permutation classes. This characterisation allows us to give a new short proof of the Fibonacci dichotomy the number of permutations of length n in a permutation class is either at least as large as the nth Fibonacci number or is eventually polynomial. 1 Introduction A permutation of n 1 contains the permutation a of k a if has a subsequence of length k in the same relative order as a. For example 391867452 written in list or one-line notation contains a 51342 as can be seen by considering the subsequence 91672 2 3 5 6 9 . A permutation class is a downset of permutations under this order or in other words if C is a permutation class 2 C and a then a 2 C. We shall denote by Cn n 2 N the set C n Sn . those permutations in C of length n. Recall that an antichain is a set of pairwise incomparable elements. For any permutation class C there is a unique and possibly infinite antichain B such that C Av B 3 for all 3 2 B . This antichain B is called the basis of C. Permutation classes arise naturally in a variety of disparate fields ranging from the analysis of sorting machines dating back to Knuth 13 who proved that a permutation is Supported by a Royal Society Dorothy Hodgkin Research Fellowship. Supported by EPSRC grant GR S53503 01. 1Here n 1 2 . n and more generally for a b 2 N a b the interval a a 1 . b is denoted by a b the interval a 1 a 2 . b is denoted by a b and so on. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R54 1 Figure 1 The plot of downset in N2 the elements of .