Pattern avoidance classes and subpermutations

MaRDI QIDQ2583660zbMATH OpenFDO

Authors Mike Atkinson, N. Ruškuc, Maximillian M. Murphy

Publication date 17 January 2006

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

Full work available at URL https://arxiv.org/abs/math/0402186, https://eudml.org/doc/125571, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r60.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

permutation patternsrestricted permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Abstract: Pattern avoidance classes of permutations that cannot be expressed as unions of proper subclasses can be described as the set of subpermutations of a single bijection. In the case that this bijection is a permutation of the natural numbers a structure theorem is given. The structure theorem shows that the class is almost closed under direct sums or has a rational generating function.

Review text

The paper under review gives a structural theorem for classes of permutations defined by their avoiding a given set of permutation patterns. The authors call a pattern-avoidance class atomic if it cannot be expressed as a union of proper subclasses. They show that the atomic classes are precisely the classes that arise as the set of restrictions of some injection from one ordered set to another. The main theorem is a characterization of such injection and classes in the case when the order types are those of the natural numbers.

Recommendations

• Pattern classes of permutations via bijections between linearly ordered sets
• scientific article; zbMATH DE number 5870282
• Permutation classes and polyomino classes with excluded submatrices
• Pattern avoidance in poset permutations
• Substitution-closed pattern classes

Cited in

(8)

• Classical length-5 pattern-avoiding permutations
• Isomorphisms between pattern classes
• Pattern classes of permutations via bijections between linearly ordered sets
• Geometric grid classes of permutations
• Permutation classes and polyomino classes with excluded submatrices
• On the sub-permutations of pattern avoiding permutations
• Splittings and Ramsey properties of permutation classes
• Embedding dualities for set partitions and for relational structures

This page was built for publication: Pattern avoidance classes and subpermutations

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