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

Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

2 Citations (Scopus)

Abstract

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α(n)),/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α(n)), 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.

Original languageEnglish
Title of host publicationProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsDavid P. Woodruff
PublisherSociety for Industrial and Applied Mathematics
Pages133-149
Number of pages17
ISBN (Electronic)978-1-61197-791-2
DOIs
Publication statusPublished - 2024
MoE publication typeA4 Conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Alexandria, United States
Duration: 7 Jan 202410 Jan 2024
Conference number: 35

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CityAlexandria
Period07/01/202410/01/2024

Fingerprint

Dive into the research topics of 'Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns'. Together they form a unique fingerprint.
  • ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

    Chalermsook, P. (Principal investigator), Jindal, G. (Project Member), Franck, M. (Project Member), Khodamoradi, K. (Project Member), Yingchareonthawornchai, S. (Project Member), Gadekar, A. (Project Member), Orgo, L. (Project Member), Jiamjitrak, W. (Project Member) & Spoerhase, J. (Project Member)

    01/02/201831/01/2024

    Project: EU: ERC grants

Cite this