Large infinite antichains of permutations

zbMATH Open1313.05001arXiv1212.3346MaRDI QIDQ2937640FDOQ2937640

Authors: Robert Brignall, Michael Albert, Vincent Vatter 

Publication date: 9 January 2015

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.

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

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

zbMATH Keywords

permutationgenerating functionhereditary propertyantichain

Mathematics Subject Classification ID

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

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)