A mean identity for longest increasing subsequence problems

2000/04/12 by Eric M. Rains, Rains, Eric M. · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.math/0004082

15 pages, LaTeX. Continuous limits consolidated, other minor changes

openalex publication_date 2000/04/12 · arxiv created 2000/10/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that a wide variety of generalized increasing subsequence problems admit a one parameter family of extensions for which we can exactly compute the mean length of the longest increasing subsequence. By the nature of the extension, this gives upper bounds on the mean in the unextended model, which turn out to be asymptotically tight for all of the models that have so far been analyzed. A heuristic analysis based on this fact gives not just the asymptotic mean but also the asymptotic scale factor, again agreeing with all known cases.

Cited by

• Flats, spikes and crevices: the evolving shape of the inhomogeneous\n corner growth model

Related

• The longest increasing subsequence in involutions avoiding 3412 and another pattern
• Finite size corrections relating to distributions of the length of longest increasing subsequences
• Asymptotic expansions relating to the lengths of longest monotone subsequences of involutions
• Longest Increasing Subsequence under Persistent Comparison Errors
• Asymptotics of the Longest Increasing Subsequence in Random Permutations