Polynomial separable index for pattern-avoiding permutations
Question 1.2 · arXiv:2308.02981
Status open high confidence
The source paper (SODA 2024) establishes a doubly exponential upper bound 2^{2^{O(k)}} on the separable index of permutations avoiding a pattern of size k, while Fox's results give a lower bound of Omega(k^{1/4-epsilon}). Question 1.2 asks whether a polynomial upper bound holds, closing this large gap. No follow-up work resolving this question was found in a search of the literature through May 2026.
Reviewer notes. No follow-up found resolving Question 1.2. The paper appeared at SODA 2024. The question is recent (2023) and the gap between the doubly-exponential upper bound and the polynomial lower bound is still unresolved as of the search. Colin Geniet's 2024 PhD thesis (hal-04643807) may contain related material but was inaccessible during this review.
Context
The authors' main theorem gives a doubly exponential upper bound $2^{2^{O(k)}}$ on the separable index of permutations avoiding a pattern of size $k$. Lower bounds from Fox's results on growth of pattern-avoiding classes show the maximum separable index is at least $\Omega(k^{1/4-\varepsilon})$ for any $\varepsilon > 0$, leaving a large gap. The question asks whether a polynomial upper bound might hold.
Source paper
Factoring Pattern-Free Permutations into Separable ones
Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé · 2023-08-06
https://arxiv.org/abs/2308.02981
PDF source