Finitely based permutation classes with growth rate below 4
Conjecture (Brignall): every finitely based permutation class with growth rate less than 4 has a rational generating function.
Cite
@misc{cairn-rational-permutation-classes-below-four,
title = {Finitely based permutation classes with growth rate below 4},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/rational-permutation-classes-below-four}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/rational-permutation-classes-below-four)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
A permutation class is finitely based if it is defined by avoiding finitely many patterns, and rational if its generating function is rational. Conjecture: every finitely based class with growth rate < 4 is rational.
What is known
All finitely based subclasses of Av(123) are rational; classes inside the separable permutations that avoid containing Av(132) (and its symmetries) are strongly rational. Growth rate 4 is where non-rational behaviour can start.
What counts as progress
- Proofs for further families of finitely based classes.
- A counterexample: a finitely based class of growth rate below 4 with a provably non-rational generating function.
- Computational surveys of classes with small bases (enumeration, guessed generating functions).
Source. Posed by Robert Brignall in the open problem session of the Oberwolfach workshop Mini-Workshop: Permutation Patterns (2024), recorded in Oberwolfach Reports 6/2024, p. 286 (EMS Press, DOI 10.4171/OWR/2024/6), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.