Enumeration Complexity of Permutation Classes
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},…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.37940
curl -X POST /api/v1/records/arxiv/2610.37940/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.37940/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'