Profile classes and partial well-order for permutations

MaRDI QIDQ1422040zbMATH OpenFDO

Authors Maximillian M. Murphy, Vincent Vatter

Publication date 3 February 2004

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0310321, https://eudml.org/doc/123375, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i2r17.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

well-quasi-orderrestricted permutationpartial well-orderforbidden subsequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partial orders, general (06A06) Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07)

Abstract: It is known that the set of permutations, under the pattern containment ordering, is not a partial well-order. Characterizing the partially well-ordered closed sets (equivalently: down sets or ideals) in this poset remains a wide-open problem. Given a 0/+-1 matrix M, we define a closed set of permutations called the profile class of M. These sets are generalizations of sets considered by Atkinson, Murphy, and Ruskuc. We show that the profile class of M is partially well-ordered if and only if a related graph is a forest. Related to the antichains we construct to prove one of the directions of this result, we construct exotic fundamental antichains, which lack the periodicity exhibited by all previously known fundamental antichains of permutations.

Recommendations

• Partially well-ordered closed sets of permutations
• Grid classes and partial well order
• On partial well-order for monotone grid classes of permutations
• Well-quasi-order for permutation graphs omitting a path and a clique
• An infinite antichain of permutations

Cited in

(18)

• Letter graphs and geometric grid classes of permutations
• Pattern classes of permutations via bijections between linearly ordered sets
• An antichain of monomial ideals in a twisted commutative algebra
• On partial well-order for monotone grid classes of permutations
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Labelled well-quasi-order for permutation classes
• Grid classes and partial well order
• Arc permutations
• Boundary properties of well-quasi-ordered sets of graphs
• Profile and hereditary classes of ordered relational structures
• Profiles of permutations
• Well-quasi-order for permutation graphs omitting a path and a clique
• Forbidden substructures and combinatorial dichotomies: WQO and universality
• Geometric grid classes of permutations
• Partially well-ordered closed sets of permutations
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• Juxtaposing Catalan permutation classes with monotone ones
• Fibonacci numbers, consecutive patterns, and inverse peaks

This page was built for publication: Profile classes and partial well-order for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422040)