Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
share
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