Abstract:

A permutation is an ( r , s )- permutation if it can be partitioned into r increasing and s decreasing, possibly empty subsequences. For any fixed non-negative integers r and s , the family of ( r , s )-permutations is characterized by a finite list of forbidden subsequences. This is derived from a more general graph-theoretic proof showing that, for any fixed non-negative integers r and s , the family of perfect graphs whose vertex set admits a partition into r cliques and s independent sets if characterized by a finite list of forbidden induced subgraphs.

Language: English

Document Type: Miscellaneous

Affiliations: 1: Department of Mathematics, University of Louisville, Louisville, Kentucky, 40292 2: Department of Mathematics and Statistics, University of Idaho, Moscow, Idaho, 83844 3: Department of Mathematics, University of Louisville, Louisville, Kentucky, 40292