Partitioning Permutations into Increasing and Decreasing Subsequences

Authors: Kezdy A.E.1; Snevily H.S.2; Wang C.3

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

Publisher: Academic Press

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

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

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$59.66 plus tax

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A