Partitioning Permutations into Increasing and Decreasing Subsequences

Authors: Kezdy A.E.¹; Snevily H.S.²; Wang C.³

Source: Journal of Combinatorial Theory, Series A, Volume 73, Number 1, February 1996 , pp. 353-359(7)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

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

Publication date: 1996-02-01