Uncountably many enumerations of well-quasi-ordered permutation classes

Combinatorial Theory 2026 Open access

Read full text
Authors: Robert Brignall, Vincent R. Vatter
DOI: 10.5070/c66165703
Cited by: 0

Abstract

We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.Mathematics Subject Classifications: 05A05, 05A15, 06A07Keywords: Generating functions, permutation classes, well-quasi-order

Fields of Study & Subjects

Coding theory and cryptography semigroups and automata theory Advanced Combinatorial Mathematics

Publication details

Journal / source
Combinatorial Theory
Volume
6
Issue
1
Publication date
20 April 2026
Language
EN