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 kpermutation π. 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 ExpP π b ´‚ ‚ ‚ ¯, nq. This is the maximum number of 1s in an n ˆn 0-1 matrix avoiding P π b ´‚ ‚ ‚ ¯, where P π is the k ˆk permutation matrix of π, and P π b ´‚ ‚ ‚ ¯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

where αpnq is the inverse-Ackermann function. In this paper we give nearly tight upper and lower bounds on the density of P π b ´‚ ‚ ‚ ¯-free matrices in terms of "n", and improve the dependence on "k" from doubly exponential to singly exponential.

As a consequence, sorting π-free sequences can be performed in Opn2 p1`op1qqαpnq q 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.