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

07/05/2023
by   Parinya Chalermsook, et al.
0

We consider the problem of comparison-sorting an n-permutation S that avoids some k-permutation π. 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 Ex(P_π⊗hat,n). This is the maximum number of 1s in an n× n 0-1 matrix avoiding P_π⊗hat, where P_π is the k× k permutation matrix of π, ⊗ the Kronecker product, and hat = ([ ∙; ∙ ∙ ]). 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_π⊗hat-free matrices in terms of the inverse-Ackermann function α(n). Ex(P_π⊗hat,n) = {[ Ω(n· 2^α(n)), ; O(n· 2^O(k^2)+(1+o(1))α(n)), ]. 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset