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

We consider the problem of comparison-sorting an n-permutation S that avoids some k-permutation π. Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak [CGK⁺15b] prove that when S is sorted by inserting the elements into the GreedyFuture [DHI⁺09] binary search tree, the running time is linear in the extremal function Ex(Pπ ☉ (_•^•_•), n). This is the maximum number of 1s in an n * n 0-1 matrix avoiding Pπ ☉ (_•^•_•), where Pπ is the k * k permutation matrix of π, and Pπ ☉ (_•^•_•) is the 2k * 3k Kronecker product of Pπ and the “hat” pattern (_•^•_•). The same time bound can be achieved by sorting S with Kozma and Saranurak's SmoothHeap [KS20]. Applying off-the-shelf results on the extremal functions of 0-1 matrices, it was known that Ex(Pπ ☉ (_•^•_•), n) = { Ω ( n · 2α⁽ⁿ⁾),/O( n · 2α^{(n))3k/2-O(1)}) where α(n) is the inverse-Ackermann function. In this paper we give nearly tight upper and lower bounds on the density of Pπ ☉ (_•^•_•) -free matrices in terms of “n”, and improve the dependence on “k” from doubly exponential to singly exponential. Ex(Pπ ☉ (_•^•_•), n) = { Ω ( n · 2α⁽ⁿ⁾), for most π,/O ( n · 2O^{(k2)+(1+o(1))α(n)}), for all π. As a consequence, sorting π-free sequences can be performed in O(n2^{(1+o(1))α(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.