{"ID":2923658,"CreatedAt":"2026-06-02T04:05:25.881865328Z","UpdatedAt":"2026-06-04T13:12:39.622923895Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.02263","arxiv_id":"2606.02263","title":"Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence","abstract":"We study exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has prescribed length $k$. For $k \\in Θ(n)$, we give a direct rejection sampler whose expected running time is $O(n\\log\\log n)$ in the word-RAM model. The sampler uses an expanded proposal space consisting of permutations together with a specified increasing subsequence, and accepts exactly those proposals whose specified subsequence is the leftmost LIS. For arbitrary $1\\le k\\le n$, we give an exact sampler based on the Robinson--Schensted correspondence. The algorithm samples the corresponding Plancherel-conditioned shape by computing exact completion counts via determinant identities, and then samples two uniform tableaux of that shape. The direct implementation runs in $\\tilde O(n^4k^5)$ expected time. We then show that the same sampler can be implemented in expected $\\tilde O(n^3k^4)$ time by evaluating a determinant oracle through Hankel moment matrices.","short_abstract":"We study exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has prescribed length $k$. For $k \\in Θ(n)$, we give a direct rejection sampler whose expected running time is $O(n\\log\\log n)$ in the word-RAM model. The sampler uses an expanded proposal space consisting of permut...","url_abs":"https://arxiv.org/abs/2606.02263","url_pdf":"https://arxiv.org/pdf/2606.02263v1","authors":"[\"Peter Clifford\",\"Raphaël Clifford\"]","published":"2026-06-01T13:50:04Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}