# Hierarchical sorting strategies for pattern-avoiding permutations?

For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \mathcal{C} \cap S_n$.

In particular, when $\mathcal{C}$ is closed by subpatterns, it follows by Marcus-Tardos theorem (refined by J. Fox) that $|\mathcal{C}_n| \leq C^n$ where $C$ is the Stanley-Wilf constant of $\mathcal{C}$. This leads to the following question: is it possible to sort such a class using at most $O(n \log C)$ comparisons? This question is a strengthening of Question 1 in the paper 'Fast Sorting and Pattern-avoiding Permutations' by D. Arthur.

It seems possible to represent such a sorting strategy by a binary tree which would essentially mimic an 'unbalanced' merge-sort algorithm. Here is the idea: given a permutation $\pi$, we would look for a tree $T_{\pi}$ leaf-labeled by the points of $\pi$, such that for each node $u$ of $T_{\pi}$ the 'overlap' between the two child subtrees would be $O(\log C)$ (either worst-case or on average). However I suspect that a more involved structure is necessary to solve this problem; should it admit a positive solution.

• What do you mean by "closed by subpatterns"? Is this anything different from avoiding a fixed pattern? – Sasho Nikolov Apr 22 '14 at 11:49
• By the reference to Stanley-Wilf, it seems that this is exactly what is intended. – Suresh Venkat Apr 22 '14 at 20:09
• A related question: when is it possible to represent a class of permutations avoiding a pattern $\beta$ in $n\log C$ bits ? – Suresh Venkat Apr 22 '14 at 20:10
• @SashoNikolov: I meant closure under the 'involvement' relation as it is commonly called; this is equivalent to avoiding a (possibly infinite) set of patterns. – NisaiVloot Apr 23 '14 at 20:49
• @SureshVenkat: it is feasible for specific classes admitting a tree- or word- based representation; solving the general case with a poly-time representation is open as far as I know. In the language of combinatorial enumeration, this is a ranking/unranking problem, while the related listing problem can be done efficiently through generating trees. – NisaiVloot Apr 23 '14 at 20:50

Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C_{i-1} C_{n-i}$, and this gives a recursive algorithm for encoding $231$-avoiding permutations: divide the interval $[0,C_n)$ into $n$ intervals $I_1,\ldots,I_n$ of lengths $C_i C_{n-i-1}$ for $i=1,\ldots,n$ arbitrarily. Given a permutation with $\pi^{-1}(n) = i$, notice that $\pi|_{1,\ldots,i-1}$ is a $231$-avoiding permutation of $\{1,\ldots,i-1\}$, and $\pi|_{i+1,\ldots,n}$ is a $231$-avoiding permutation of $\{i+1,\ldots,n\}$. Recursively encode the first part in $[0,C_{i-1})$ and the second part in $[0,C_{n-i})$, and put both encodings together to encode $\pi$ in $I_i$.
For any other $\tau \in S_3$, $\tau$-avoiding permutations are bijectively related to $231$-avoiding permutations, through taking the inverse, complementing the elements, reversing, or the Simion–Schmidt bijection between $132$- and $123$-avoiding permutations. So this encoding applies to all patterns of length $3$.