← All problems

Proper growth-rate conjecture for permutation classes

Let C\mathcal{C} be a proper permutation class, meaning a class of finite permutations closed under taking patterns and satisfying C≠Av⁡(∅)\mathcal{C}\neq\operatorname{Av}(\varnothing), where Av⁡(∅)\operatorname{Av}(\varnothing) is the class of all finite permutations. Then the limit lim⁡n→∞∣C∩Sn∣1/n\lim_{n\to\infty}|\mathcal{C}\cap S_n|^{1/n} exists and is finite.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to have found a counterexample showing that the exponential growth rate of every proper permutation class need not converge.

The conjecture asserts that every proper permutation class has a convergent nth-root growth rate. No proposer or original date is identified in the retrieved sources.

Known results

  • Kaiser and Klazar (2003) sharply restricted class speeds below 22, including a classification of possible values.
  • Vatter characterized growth rates below κ≈2.20557\kappa \approx 2.20557, where κ\kappa is the positive root of x3−2x2−1x^{3}-2x^{2}-1.
  • Below ξ≈2.30522\xi \approx 2.30522, every growth rate is achieved by a sum-closed class, although uncountably many occur arbitrarily near ξ\xi.

October 2026 claimed counterexample

Jay Pantone and Vincent Vatter’s preprint Permutation classes need not have proper growth rates claims a counterexample to universal convergence and an analogous ordered-graph result. The claim is unrefereed and has no independent mathematical assessment in the retrieved evidence.

Current status (as of October 2026): Universal convergence is claimed false by an unrefereed preprint, but the counterexample remains unverified, so the problem is not independently settled.

Sources

Solutions 0

No solutions have been posted yet.