Jay Pantone

Deflatability of Permutation Classes

A permutation class is said to be deflatable if its simple permutations are contained within a proper subclass. Deflatable classes are often easier to describe, analyze, and enumerate than their non-deflatable counterparts. This paper presents theorems guaranteeing the non-deflatability of principal classes, constructs an infinite family of deflatable principal classes, and provides examples of each.

Acknowledgments

The authors are grateful to Vince Vatter for participating in discussions which furthered this research. In particular he was in part responsible for the original proof of Proposition 3.10 which convinced us that "except in trivial cases principal classes aren't deflatable" was perhaps not as obvious or as easy as one might initially think -- and indeed of course we now know it to be false. Additionally, Cheyne Homberger and Jay Pantone wish to thank Michael Albert and Mike Atkinson for their hospitality at the University of Otago in March and April of 2014.

Open Questions
• Is there a permutation class with a positive density of simple permutations?
• We prove in Section 3 that the principal class $$\text{Av}(\pi)$$ is non-deflatable if any of the following conditions are met:
• $$\pi$$ can be written as a sum of three or more permutations,
• $$\pi$$ can be written as the sum of two permutations, each of size greater than $$1$$, or
• $$\pi = 1 \oplus \rho$$ where $$|\rho| \geq 3$$ and $$\rho$$ contains either no decreasing bond, or no increasing bond, where a bond is an interval of size $$2$$.
• This does not completely classify the non-deflatable principal classes, as shown by the non-deflatability of $$\text{Av}(2413)$$ (Proposition 3.10). Hence we ask, which principal classes are non-deflatable? Questions 5.1 and 5.2 list the permutations $$\pi$$ of lengths $$5$$ and $$6$$ for which it is not known whether $$\text{Av}(\pi)$$ is deflatable.
• In Section 4, we provide witnesses of deflatability for the classes
• $$\text{Av}(246135)$$,
• $$\text{Av}(24681357)$$,
• $$\text{Av}(2\;4\;6\;8\;10\;1\;3\;5\;7\;9)$$,
• $$\text{Av}(2\;4\;6\;8\;10\;12\;1\;3\;5\;7\;9\;11)$$,
• $$\text{Av}(2\;4\;6\;8\;10\;12\;14\;1\;3\;5\;7\;9\;11\;13)$$.
Is there a family of permutations that are witnesses of deflatability for $$\text{Av}(246\ldots(2n)135\ldots(2n-1))$$ for all $$n$$?