The Longest Increasing Subsequence Problem revisited

Silvio Franz, Roberto Mulet · 2026

Read The Longest Increasing Subsequence Problem revisited by Silvio Franz, Roberto Mulet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01501.txt.

Introduction

Franz and Mulet revisit a classic problem: the longest increasing subsequence. They study it at a set temperature, as in statistical mechanics. Two energy scales stand out in their results. A Schottky-like crossover marks the first scale. A condensation transition marks the second, at lower temperature. Below it, the count of longest configurations grows slower than exponential. Exact algorithms solve the ground state in polynomial time, they note.

Yet local Monte Carlo moves get trapped after fast quenches. The stuck states show glassy signs at low temperature. Two-step relaxation, stuck overlaps, and aging all appear. Slow logarithmic annealing tracks the true balance down to the ground state. Sparse counts, not energy barriers, make local search fail here.

Catalog record

CREATORSilvio Franz, Roberto Mulet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01501

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Longest Increasing Subsequence Problem revisited Silvio Franz, Roberto Mulet Abstract The Longest Increasing Subsequence (LIS) problem—a classic combinatorial challenge with deep connections to statistical mechanics—exhibits a rich thermodynamic landscape. Introducing a temperature we identify two distinct energy scales: a Schottky-like crossover at T cross T_{\text{cross}} and a condensation transition at T cond T_{\text{cond}} , below which the number of maximum-length configurations becomes sub-exponential in system size. We also show that despite the existence of polynomial-time dynamic programming algorithms for the ground state, local Monte Carlo dynamics, after sudden quenches at low temperatures, become trapped in metastable state configuration displaying characteristic glassy signatures: two-step relaxation, persistent dynamical overlaps, and aging. On the other hand, logarithmic annealing tracks equilibrium down to the ground state. These results establish that thermodynamic sparsity—not energetic barriers—can render local search dynamically intractable, positioning the LIS problem as a bridge between exactly solvable optimization and glassy spin-glass phenomenology. I Introduction Given a sequence of distinct numbers, the Longest Increasing Subsequence Problem (LISP) seeks to determine the length of the longest subsequence that is strictly increasing. First suggested by Ulam in 1961 12 , the LIS problem has since revealed connections at the intersection of mathematics 2 , computer science 13 , and statistical physics 10 . The asymptotic behavior of longest increasing subsequence lengths in random permutations is governed by the Baik–Deift–Johansson theorem 1 , which establishes a connection to random matrix theory: when properly centered and scaled as \ell_{\max}=2\sqrt{N}+N^{1/6}\chi , the fluctuations converge to the Tracy–Widom distribution for the Gaussian Unitary Ensemble 11 . This universality extends further—Práhofer and Spohn 10 demonstrated that LIS length fluctuations belong to the Kardar–Parisi–Zhang (KPZ). The relevance of this result can not be underestimated, it connects the LISP to a broad family of stochastic processes exhibiting identical scaling exponents and fluctuation statistics, including models of interface growth, stochastic surface dynamics, and one-dimensional asymmetric transport such as the asymmetric simple exclusion process (ASEP) 6 ; 4 Recent work has uncovered an even richer solution-space structure. Krabbe et al. 7 showed that the entropy of longest increasing subsequences follows a Gaussian distribution with significant tail deviations. Surprisingly, in Ref. 8 , extending the problem to a thermodynamic framework, the authors interpret their results as signatures of replica symmetry breaking (RSB), a hallmark of complex energy landscapes typically associated with spin glasses and disordered systems 9 . This apparent contradiction between KPZ universality and the possibility of replica symmetry breaking motivates our investigation into the thermodynamic properties of the LIS problem and, simultaneously, the dynamical behavior of local search algorithms designed to solve it. While directed polymers in random media (DPRM) in 1+1 dimensions, a paradigmatic KPZ system, has no finite-T phase transitions 5 , the possibility of an RSB transition suggests that correlations intrinsic to subsequence construction and the discrete combinatorial nature of LIS may yield fundamentally different behavior. We follow Krabbe’s et al. 7 and consider the length of increasing subsequences as an energy function. We then introduce a temperature parameter to probe the system’s behavior across different energy scales. Our results reveal a complex phase diagram featuring two distinct temperatures: (i) we confirm the presence of a crossover at T_{\text{cross}}\approx 0.38 , and (ii) remarkably, a condensation transition at T_{\text{cond}}=0.10\pm 0.02 where the system condensates into a sub-exponential number of ground states. Furthermore, we study also the dynamical behavior of the model under local Metropolis rules satisfying detailed balance and show that this temperature signal the appearance of glassy dynamics characteristic of complex systems. II The Model Given a sequence of independent and identically distributed random numbers \{s_{i}\} for i=1,\dots,N , Ulam’s problem seeks the length of the longest increasing subsequence. An elegant formulation views the problem as a directed polymer on a random graph that can be solved in polynomial time by dynamic programming. Define L(i) as the length of the longest increasing subsequence ending at position i , which satisfies the recurrence: L(i)=1+\max_{\begin{subarray}{c}1\leq j<i\\ H_{ij}=1\end{subarray}}L(j), (1) with L(1)=1 , and where H_{i,j}=\Theta(s_{i}-s_{j}) indicates whether s_{i}>s_{j} . The overall LIS length is then L=\max_{i}L(i) . This formulation defines the set of Ulam random graphs: vertices at positions (i,s_{i}) are connected by directed edges when i<j and s_{i}<s_{j} , with H_{i,j} as its adjacency matrix. Despite the graph’s long-range connections, optimal paths use only local edges in index space, yielding a polymer length that scales as \sim 2\sqrt{N} 3 . Building on this graph formulation, we can count all increasing subsequences of length \ell via dynamic programming 8 . Let N_{i}^{\ell} be the number of such sequences ending at position i . These satisfy the recursion: \displaystyle N_{i}^{\ell} \displaystyle=\sum_{j<i}H_{ij}N_{j}^{\ell-1}, (2) \displaystyle N_{i}^{1} \displaystyle=1. (3) or, in vector form, \mathbf{N}^{\ell}=H^{\ell-1}\mathbf{N}^{1} . Notice that (H^{\ell-1})_{ij} counts directed paths of length \ell-1 from j to i in the Ulam graph. Consequently, the LIS length equals the largest \ell for which H^{\ell-1} is non-zero. Conveniently, from the multiplicities N_{i}^{\ell} , we can build a thermodynamic picture of the problem in the microcanonical formalism. Define an entropy S(\ell) as: N(\ell)=e^{\sqrt{N}S(\ell/\sqrt{N},N)}=\sum_{i=1}^{N-\ell}N_{i}^{\ell}. (4) and associate an energy E(\ell)=-\ell to each subsequence. In this microcanonical setting, the temperature and the specific heat can be computed as: \displaystyle\frac{1}{T}=\frac{\partial S}{\partial E} (5) \displaystyle C_{v}=-\frac{1}{T^{2}\frac{\partial^{2}S}{\partial E^{2}}}. (6) Notice that while the entropy is self-averaging in the thermodynamic limit, it fluctuates for finite N . Therefore to get the temperature as a function of energy with eq. ( 6 ), we measure the energy of each different sample relative to its ground state. This choice is crucial for identifying a condensation transition temperature. Alternatively, in the canonical formalism, the partition function takes the form: Z_{N}(\beta)=\sum_{\ell}N(\ell)e^{\beta\ell}=\sum_{\ell}e^{\sqrt{N}S(\ell/\sqrt{N},N)}e^{\beta\ell}. (7) and the specific heat C_{v} can be computed as the variance of the energy E=-\ell : c_{v}=\frac{\langle E^{2}\rangle-\langle E\rangle^{2}}{\sqrt{N}T^{2}} (8) where \langle\cdot\rangle denotes the average over multiple realizations of \sigma . The reader must notice the \sqrt{N} in the denominator needed to respect the scaling of the energy with the system size . We confront both, the microcanonical and the canonical, approaches in our numerical computations and found that they are equivalent. Having presented the thermodynamic formalism, we now describe a local Monte Carlo algorithm in the canonical framework of fixed temperature. The dynamics satisfies detailed balance (see Appendix A ) while preserving the increasing-subsequence constraint through elementary moves that add or remove elements. For a given temperature T , we propose new configurations using the move set in Algorithm 1 Local Algorithm: Monte Carlo update satisfying detailed balance for the LISP at temperature T . 1: Random quenched sequence A=(a_{1},a_{2},\dots,a_{N}) , current increasing sub-se quence x_{t} , temperature T>0 2: Updated sub-sequence x_{t+1} 3: 4: x\leftarrow x_{t} \triangleright Initialize working copy 5: for i=1 to N do \triangleright Perform N elementary operations 6: Select e\in A uniformly at random 7: if e\notin x then 8: Find all positions j such that inserting e at index j in x preserves increasing order 9: if such positions exist then 10: Insert e at the first valid position in x 11: end if 12: else if e\in x and |x|>1 then 13: With probability \exp(-1/T) , remove e from x 14: end if 15: end for 16: x_{t+1}\leftarrow x Algorithm 1: Monte Carlo update satisfying detailed balance for

Read the complete text