Constructs an uncountable family of well-quasi-ordered permutation classes with pairwise distinct enumeration sequences, disproving the conjecture that all such classes have algebraic generating functions.
Pattern avoidance is not P-recursive
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Let $F \subset S_k$ be a finite set of permutations and let $C_n(F)$ denote the number of permutations $\sigma$ in $S_n$ avoiding the set of patterns $F$. The Noonan-Zeilberger conjecture states that the sequence ${C_n(F)}$ is P-recursive. We use Computability Theory to disprove this conjecture.
fields
math.CO 1years
2022 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Uncountably many enumerations of well-quasi-ordered permutation classes
Constructs an uncountable family of well-quasi-ordered permutation classes with pairwise distinct enumeration sequences, disproving the conjecture that all such classes have algebraic generating functions.