Large infinite antichains of permutations

2012/12/13 by Michael H. Albert, Michael Albert, Albert, Michael H. +4 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Mathematical Dynamics and Fractals #math.CO

paper · pdf · doi:10.48550/arxiv.1212.3346

arxiv created 2012/12/17 · arxiv updated 2012/12/18

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.

Cited by

• Set Partition Patterns and the Dimension Index

Related

• An Infinite Antichain of Permutations
• Permutations sorted by a finite and an infinite stack in series
• Permutations with exactly one copy of a decreasing pattern of length k
• On the growth rate of the Stanley-Wilf limit of blockable permutations
• Growth rates of permutation classes: from countable to uncountable