Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns

Abstract

We consider the problem of comparison-sorting an $n$-permutation $S$ that avoids some $k$-permutation $\pi$. Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak prove that when $S$ is sorted by inserting the elements into the GreedyFuture binary search tree, the running time is linear in the extremal function $\mathrm{Ex}(P_{\pi }\otimes \text{hat},n)$. This is the maximum number of 1s in an $n\times n$ 0-1 matrix avoiding $P_{\pi }\otimes \text{hat}$, where $P_{\pi }$ is the $k\times k$ permutation matrix of $\pi$, $\otimes$ the Kronecker product, and $\text{hat}=\left(\begin{array}{ccc}& \bullet & \\ \bullet & & \bullet \end{array}\right)$. The same time bound can be achieved by sorting $S$ with Kozma and Saranurak's SmoothHeap. In this paper we give nearly tight upper and lower bounds on the density of $P_{\pi }\otimes \text{hat}$-free matrices in terms of the inverse-Ackermann function $\alpha (n)$. \[ \mathrm{Ex}(P_π\otimes \text{hat},n) = \left\{\begin{array}{ll} Ω(n\cdot 2^{α(n)}), & \mbox{for most $\pi$,}\\ O(n\cdot 2^{O(k^2)+(1+o(1))α(n)}), & \mbox{for all $\pi$.} \end{array}\right. \] As a consequence, sorting $\pi$-free sequences can be performed in $O(n{2}^{(1+o(1))\alpha (n)})$ time. For many corollaries of the dynamic optimality conjecture, the best analysis uses forbidden 0-1 matrix theory. Our analysis may be useful in analyzing other classes of access sequences on binary search trees.