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 pi. 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 Exp(P-pi circle times (sic), n). This is the maximum number of 1s in an n x n 0-1 matrix avoiding P pi circle times (sic) , where P-pi is the k x k permutation matrix of pi, and P-pi circle times (sic) is the 2k x 3k Kronecker product of P-pi and the "hat" pattern (sic). 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-pi circle times (sic), n) = {Omega (n alpha(n)), O((n center dot 2((alpha(n))3k/2 O(1))), where alpha(n) is the inverse-Ackermann function. In this paper we give nearly tight upper and lower bounds on the density of P-pi circle times (sic)- free matrices in terms of "n", and improve the dependence on "k" from doubly exponential to singly exponential. Ex(P-pi circle times (sic), n) = {Omega (n center dot 2(alpha(n))), for most pi O((n center dot 2(O(k2)+(1+0(1))alpha(n))), for all pi. As a consequence, sorting pi-free sequences can be performed in O(n2((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.