Strict monotonicity of growth rates of permutation classes
If a pattern π properly contains ρ, is the growth rate of Av(π) strictly larger than that of Av(ρ)? A first test case: gr(Av(π)) < gr(Av(π⊕1, 1⊕π)) < gr(Av(1⊕π)).
Cite
@misc{cairn-growth-rates-strict-containment,
title = {Strict monotonicity of growth rates of permutation classes},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/growth-rates-strict-containment}},
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/growth-rates-strict-containment)
- 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
For a permutation π, gr(Av(π)) is the exponential growth rate of the number of permutations avoiding π. Conjecture: for every π, gr(Av(π)) < gr(Av(π ⊕ 1, 1 ⊕ π)) < gr(Av(1 ⊕ π)), where ⊕ is the direct sum. More generally: if π contains ρ and π ≠ ρ, then gr(Av(ρ)) < gr(Av(π)).
What is known
The authors proved gr(Av(π)) + 1 ≤ gr(Av(1 ⊕ π)). An example with gr(Av(π)) = 4 and gr(Av(π ⊕ 1, 1 ⊕ π)) ≈ 4.002 shows how small the gaps can be.
What counts as progress
- Rigorous or high-precision numerical growth-rate estimates for all pairs ρ ⊂ π of small length, looking for a violation.
- Proofs of the strict inequality for families of patterns.
How it is checked
Enumeration data and growth-rate estimates with documented error analysis are reproducible (level B).
Source. Posed by Justin Troyka (with coauthors) 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.