2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27228 2026-08-25T13:18:18Z ddc:004 open_access

Compact Representations of Pattern-Avoiding Permutations Kozma, László Opler, Michal pattern-avoiding permutations compact data structures succinct data structures range counting twin-width Pattern-avoiding permutations are a central object of study in both combinatorics and theoretical computer science. In this paper we design a data structure that can store any size-n permutation τ that avoids an arbitrary (and unknown) fixed pattern π in the asymptotically optimal 𝒪(n lg{s_π}) bits, where s_π is the Stanley-Wilf limit of π. Our data structure supports τ(i) and τ^{-1}(i) queries in 𝒪(1) time, sidestepping the lower bounds that hold for general permutations. Comparable results were previously known only in more restricted cases, e.g., when τ is separable, which means avoiding the patterns 2413 and 3142. We also extend our data structure to support more complex geometric queries on pattern-avoiding permutations (or planar point sets) such as rectangle range counting in 𝒪(lg lg n) time. This result circumvents the lower bound of Ω(lg{n}/lg lg{n}) by Pătraşcu (STOC 2007) for the general case. For bounded treewidth permutation classes (which include the above-mentioned separable class), we further reduce the space overhead to a lower order additive term, making our data structure succinct. This extends and improves results of Chakraborty et al. (ISAAC 2024) obtained for separable permutations via different techniques. All our data structures can be constructed in linear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik László Kozma and Michal Opler 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.92 urn:nbn:de:0030-drops-272285 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.92 eng https://creativecommons.org/licenses/by/4.0/legalcode