Restricted Permutations

Michael David Atkinson

Research output: Contribution to journalArticlepeer-review

70 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)27-38
JournalDiscrete Mathematics
Volume195
Issue number1-3
DOIs
Publication statusPublished - Jan 1999

Fingerprint

Dive into the research topics of 'Restricted Permutations'. Together they form a unique fingerprint.

Cite this