Large infinite antichains of permutations

MaRDI QIDQ2937640zbMATH OpenFDO

Authors Robert Brignall, Michael Albert, Vincent Vatter

Publication date 9 January 2015

Full work available at URL https://arxiv.org/abs/1212.3346

zbMATH Keywords

permutationgenerating functionhereditary propertyantichain

Mathematics Subject Classification ID

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

Abstract: Infinite antichains of permutations have long been used to construct interesting permutation classes and counterexamples. We prove the existence and detail the construction of infinite antichains with arbitrarily large growth rates. As a consequence, we show that every proper permutation class is contained in a class with a rational generating function. While this result implies the conclusion of the Marcus-Tardos theorem, that theorem is used in our proof.

Recommendations

• An infinite antichain of permutations
• Homogeneous permutations
• Small permutation classes
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Growth rates of permutation classes: from countable to uncountable

Cited in

(5)

• An infinite antichain of permutations
• An infinite antichain of planar tanglegrams
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• Bounded affine permutations. I: Pattern avoidance and enumeration

This page was built for publication: Large infinite antichains of permutations

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