<!-- NOTE: Escape underscores as \_ when 2+ appear on the same line in math --> class: center, middle # Uncountably many enumerations of well-quasi-ordered permutation classes *Comb. Th.* (to appear), [arXiv:2211.12397](https://arxiv.org/abs/2211.12397) <br /> **[Vincent Vatter](https://vincevatter.com) joint with [Robert Brignall](https://www.rbrignall.org.uk/)** .small[(the co-creators of [digit.party](https://digit.party/))] <br /> *** January 4, 2026 Joint Mathematics Meetings *** --- # Structure & enumeration .float-left[ <img src="fig-av-231.out.png" class="img-md"> ] The class [$\mathrm{Av}(231)$](https://en.wikipedia.org/wiki/Stack-sortable_permutation) is very nice. $$ f = 1+xf^2 $$ $$ f = \frac{1-\sqrt{1-4x}}{2x} $$ $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ --- # Structure & enumeration .float-right[ <img src="fig-sep-brownian.out.png" class="img-md"> ] The class of [separable permutations](https://en.wikipedia.org/wiki/Separable_permutation) is also nice. $$ f = 1 + f\_{\oplus} + f\_{\ominus} $$ $$ f\_{\oplus} = f\_{\ominus} = \frac{f^2}{1+f} $$ $$ f = 1 + x + 2 \frac{f^2}{1+f} $$ $$ f = \frac{3 - x - \sqrt{1 - 6x + x^2}}{2} $$ **Theorem ([Albert, Atkinson, and V 2011](https://doi.org/10.1112/blms/bdr022)).** _If a subclass of the separable permutations does not contain $\mathrm{Av}(231)$ or a symmetry thereof, then it has a rational generating function._ .small[*Bull. Lond. Math. Soc.*, 43(5):859–870, 2011 Figure from Bassino, Bouvel, Féray, Gerin, and Pierrot,<br /> [The Brownian limit of separable permutations](https://doi.org/10.1214/17-AOP1223), *Ann. Probab.*, 46(4):2134–2189, 2018] --- # Structure & enumeration .float-right[ <img src="fig-av-321.out.png" class="img-md"> ] The class [$\mathrm{Av}(321)$](https://math.stackexchange.com/questions/155867/penguin-brainteaser-321-avoiding-permutations) is also nice, just not quite as nice. $$ f = 1+xf^2 $$ $$ f = \frac{1-\sqrt{1-4x}}{2x} $$ $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ <br /><br /><br /> **Theorem ([Albert, Brignall, Ruškuc, and V 2019](https://doi.org/10.1016/j.ejc.2019.01.001)).** _If a subclass of $\mathrm{Av}(321)$ is finitely based or well-quasi-ordered, then it has a rational generating function._ .small[*European J. Combin.*, 78:44–72, 2019] --- # Infinite antichains & WQO .float-right[ <img src="fig-anti1.out.png" class="img-md"> ] An **antichain** is a set of pairwise incomparable permutations. A class is **well-quasi-ordered (WQO)** if it does **not** contain an infinite antichain. .float-left[ <img src="fig-anti2.out.png" class="img-md"> ] <br /> <br /> <br /> <br /> **Examples:** - $\mathrm{Av}(231)$ is WQO - the class of separable permutations is WQO - $\mathrm{Av}(321)$ contains infinite antichains (is not WQO) --- # Infinite antichains & WQO .float-right[ <img src="fig-anti3.out.png" class="img-md"> ] An **antichain** is a set of pairwise incomparable permutations. A class is **well-quasi-ordered (WQO)** if it does **not** contain an infinite antichain. .float-left[ <img src="fig-anti4.out.png" class="img-md"> ] <br /> <br /> <br /> <br /> **Examples:** - $\mathrm{Av}(231)$ is WQO - the class of separable permutations is WQO - $\mathrm{Av}(321)$ contains infinite antichains (is not WQO) --- # Structure $\nLeftarrow$ enumeration .float-right[ <img src="fig-anti-abv.out.png" class="img-md"> ] **Theorem ([Albert, Brignall, and V 2013](https://web.archive.org/web/20141217234426/http://puma.dimai.unifi.it/24_2/albert_brignall_vatter.pdf)).** _Every proper permutation class is contained in a permutation class with a rational generating function._ .small[*Pure Math. Appl. (PU.M.A.)*, 24(2):47–57, 2013] Classes can have nice enumeration without having nice structure. Proof sketch: * Build very large antichains * Whose closures have rational generating functions * By the Marcus–Tardos theorem, every proper permutation class fits in one of these * Then prune antichain members as needed --- # Not all classes have nice enumeration **False Conjecture ([Noonan and Zeilberger 1996](https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/forbid.html)).** _Every finitely based permutation class has a D-finite generating function._ <br /> The finitely based hypothesis is necessary. Because there are infinite antichains of permutations, there are uncountably many permutation classes with distinct enumerations. They can't all have D-finite generating functions. <br /> **Theorem ([Garrabrant and Pak 2016](https://doi.org/10.1137/1.9781611974331.ch66)).** _There are finitely based permutation classes without D-finite generating functions._ --- # Structure $\stackrel{\tiny ?}{\Rightarrow}$ enumeration **Conjecture ([V 2015](http://doi.org/10.1201/b18255-18)).** _Every WQO permutation class has an algebraic generating function._ .small[In M. Bóna, ed., *Handbook of Enumerative Combinatorics*, pp. 754–833. CRC Press, Boca Raton, Florida, 2015] --- # Structure $\stackrel{\tiny ?}{\Rightarrow}$ enumeration **False Conjecture ([V 2015](http://doi.org/10.1201/b18255-18)).** _Every WQO permutation class has an algebraic generating function._ .small[In M. Bóna, ed., *Handbook of Enumerative Combinatorics*, pp. 754–833. CRC Press, Boca Raton, Florida, 2015] <br /> **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _**Not** every WQO permutation class has an algebraic generating function._ <br /> **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _There is an uncountable collection of WQO permutation classes, each with a different enumeration sequence._ .small[*Comb. Th.* (to appear)] --- # Building on Pouzet's work Maurice Pouzet had a [75th birthday conference](https://web.archive.org/web/20220817101308/algos2020.loria.fr/index.html) in 2020, so he's done quite a bit of mathematics. We build on work in his _thesis_: > Sur la théorie des relations, M. Pouzet, PhD thesis, Université Claude-Bernard (Lyon 1), 1978. Pouzet's work concerns the **factor order** on **binary words**. For words $u,w\in\\{0,1\\}^\ast$, we write $u\le w$ if $$ w=w_1uw_2 $$ for possibly empty words $w_1,w_2\in\\{0,1\\}^*$. Given a word $w\in\\{0,1\\}^\ast$, we write $\overline{w}$ for its **complement** (swaps $0$s and $1$s). Example: $$ \overline{0110}=1001. $$ --- # Pouzet's construction Let $(s\_k)\_{k\in\mathbb{N}}$ be a sequence of positive integers. We make a sequence $(\alpha\_i^{(s\_k)})\_{i\in\mathbb{N}}$ of binary words: $$ \alpha\_1^{(s\_k)} = 01 $$ $$ \alpha\_2^{(s\_k)} = \underbrace{\alpha\_1^{(s\_k)}\cdots\alpha\_1^{(s\_k)}}\_{\text{$s\_1$ copies}}\ \ \underbrace{\overline{\alpha}\_1^{(s\_k)}\cdots\overline{\alpha}\_1^{(s\_k)}}\_{\text{$s\_1$ copies}} $$ $$ \alpha\_3^{(s\_k)} = \underbrace{\alpha\_2^{(s\_k)}\cdots\alpha\_2^{(s\_k)}}\_{\text{$s\_2$ copies}}\ \ \underbrace{\overline{\alpha}\_2^{(s\_k)}\cdots\overline{\alpha}\_2^{(s\_k)}}\_{\text{$s\_2$ copies}} $$ $$ \vdots $$ -- Suppose $(s\_k)=(1,1,1,\dots)$. Then: $$ \begin{aligned} \alpha\_1^{(s\_k)} &= 01 \\\\ \alpha\_2^{(s\_k)} &= 01\ 10 \\\\ \alpha\_3^{(s\_k)} &= 0110\ 1001 \end{aligned} $$ --- # Pouzet's construction Suppose $(s\_k)=(1,1,1,\dots)$. Then: $$ \begin{aligned} \alpha\_1^{(s\_k)} &= 01 \\\\ \alpha\_2^{(s\_k)} &= 01\ 10 \\\\ \alpha\_3^{(s\_k)} &= 0110\ 1001 \end{aligned} $$ Define $$ \mathcal{L}^{(s\_k)} = \\{w\in\\{0,1\\}^\ast : \text{$w$ is a factor of some $\alpha\_n^{(s\_k)}$}\\} $$ **Theorem (Pouzet 1978).** _For every sequence $(s\_k)$, the language $\mathcal{L}^{(s\_k)}$ is WQO under the factor order._ Proof sketch: * Every word in $\mathcal{L}^{(s\_k)}$ is contained in some $\alpha\_i^{(s\_k)}$. * Every long enough word in $\mathcal{L}^{(s\_k)}$ contains $\alpha\_i^{(s\_k)}$. --- # Pouzet's construction **Theorem (Pouzet 1978).** _For every sequence $(s\_k)$, the language $\mathcal{L}^{(s\_k)}$ is WQO under the factor order._ <br /> **Theorem (Pouzet 1978).** _For every two distinct sequences $(s\_k)$ and $(t\_k)$, the languages $\mathcal{L}^{(s\_k)}$ and $\mathcal{L}^{(t\_k)}$ are distinct._ <br /> **Corollary (Pouzet 1978).** _There are uncountably many WQO "word classes" under the factor order._ <br /> -- What remains for Brignall and V to do: * Establish distinct enumerations. * Translate to permutation classes. --- # Encoding factor order in permutation pattern order .float-right[ <img src="fig-rightward-pin-seq.out.png" class="img-md"> ] We encode with rightward-yearning [pin sequences](https://doi.org/10.1007/s00493-008-2314-0). In a *pin sequence*, each pin separates the previous pin from all points before it, and extends maximally in its direction (up, down, left, or right). In a *rightward-yearning pin sequence*, every second pin is *right*, and the others are *up* or *down*. <br /> --- # Encoding factor order in permutation pattern order .float-right[ <img src="fig-rightward-pin-seq-labels.out.png" class="img-md"> ] We encode with rightward-yearning [pin sequences](https://doi.org/10.1007/s00493-008-2314-0). In a *pin sequence*, each pin separates the previous pin from all points before it, and extends maximally in its direction (up, down, left, or right). In a *rightward-yearning pin sequence*, every second pin is *right*, and the others are *up* or *down*. <br /> $$ 0 \mapsto d\,r $$ $$ 1 \mapsto u\,r $$ $$ 01101001 \mapsto drururdrurdrdrur $$ --- # Permutation classes For a binary word $w$ let $\rho(w)$ be the permutation (rightward-yearning pin sequence) corresponding to $w$ under this mapping. From any sequence $(s\_k)$ of positive integers, we get a permutation class $$ \mathcal{C}^{(s\_k)} = \\{\text{permutations contained in $\rho(w)$ for some $w\in\mathcal{L}^{(s_k)}$}\\}. $$ *** After much detailed analysis of these pin sequences: **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _For every sequence $(s\_k)$, the permutation class $\mathcal{C}^{(s\_k)}$ is WQO._ **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _For every two distinct sequences $(s\_k)$ and $(t\_k)$, the permutation classes $\mathcal{C}^{(s\_k)}$ and $\mathcal{C}^{(t\_k)}$ have distinct enumeration sequences._ **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _There is an uncountable collection of WQO permutation classes, each with a different enumeration sequence._ --- # What do these classes look like? **Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).** _There is an uncountable collection of WQO permutation classes, each with a different enumeration sequence._ .float-right[ <img src="heatmap_1432_4123_len500_1m.png" class="img-md"> ] <br /> *** Almost all of these classes will be *infinitely based*. *** But they all live inside $\mathrm{Av}(1432, 4132)$, which has the very simple enumeration $$ \frac{4^{n-1}+2}{3}. $$ (The heatmap of this class is thanks to [Jay Pantone](https://jaypantone.com/) using [Combinatorial Exploration](https://arxiv.org/abs/2202.07715).) *** What about [labelled well-quasi-order](https://escholarship.org/uc/item/8579b1dq)? ***