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

forbidden subsequencepartial well-orderrestricted permutationwell-quasi-order

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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/\pm 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

(20)

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

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)