Uncountably many WQO permutation classes

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)

**[Vincent Vatter](https://vincevatter.com) joint with [Robert Brignall](https://www.rbrignall.org.uk/)**

.small[(the co-creators of [digit.party](https://digit.party/))]

***

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, 
[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}
$$

**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">
]

**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">
]

**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._

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.

**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]

**Theorem ([Brignall and V 2026+](https://arxiv.org/abs/2211.12397)).**
_**Not** every WQO permutation class has an algebraic generating function._

**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._

**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._

**Corollary (Pouzet 1978).**
_There are uncountably many WQO "word classes" under the factor order._

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*.

---

# 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*.

$$
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">
]

***

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)?

***