{"id":"arxiv/2610.37940","url":"https://arxiv.org/abs/2610.37940","tags":["cs.CC","math.CO"],"score":0,"title":"Enumeration Complexity of Permutation Classes","domain":"cs.CC","source":"arxiv","authors":["Manuel Bodirsky","Mohamed Elsheikh"],"reviews":0,"subject":"cs.CC","summary":"We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \\emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $B$. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the \\emph{insert-maximum extension problem},…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-27","reactions":{}}