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: Pattern avoidance classes and subpermutations. | Pattern avoidance classes and subpermutations M. D. Atkinson Department of Computer Science University of Otago New Zealand mike@ M. M. Murphy and N. Ruskuc School of Mathematics and Statistics University of St Andrews Scotland KY16 9SS nik@ and max@ Submitted Oct 6 2005 Accepted Nov 10 2005 Published Nov 15 2005 Mathematics Subject Classifications 05A15 05A16 Abstract Pattern avoidance classes of permutations that cannot be expressed as unions of proper subclasses can be described as the set of subpermutations of a single bijection. In the case that this bijection is a permutation of the natural numbers a structure theorem is given. The structure theorem shows that the class is almost closed under direct sums or has a rational generating function. Keywords Restricted permutations pattern avoidance subpermutations. 1 Introduction Classes of permutations defined by their avoiding a given set of permutation patterns have been intensively studied within the last decade. Quite often the issue has been to determine the number of permutations of each length in the class. In order to do this it is necessary to derive structural properties of the permutations in the class starting from the avoided set. However there are very few general techniques for obtaining such structural information. This paper is a contribution towards a general structure theory. We begin from the point of view that pattern-avoidance classes can be expressed as unions of atomic classes those that have no non-trivial expression as a union . We shall show that these atomic classes are precisely the classes that arise as the set of restrictions of some injection from one ordered set to another. In general the order types of these two sets provide some information about the atomic class. The major part of our paper is a THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R60 1 characterisation of such injections and classes in the simplest case when the order .
