Restricted Permutations

Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. They have functioned as a convenient descriptor for several sets of permutations which arise naturally in combinatorics and computer science. We study the partial order on permutations that underlies the idea of restriction and which gives rise to sets of sequences closed under taking subsequences. In applications, the question of whether a closed set has a finite 'basis' is often considered. Several constructions that respect the finite basis property are given. A family of closed sets, called profile-closed sets, is introduced and used to solve some instances of the inverse problem: describing a closed set from its basis. Some enumeration results are also given. (C) 1999 Elsevier Science B.V. All rights reserved.