Replica symmetry breaking for Ulam's problem

We study increasing subsequences (ISs) for an ensemble of sequences given by a permutation of numbers {1, 2, ... , n}. We consider a Boltzmann ensemble at temperature T. Thus each IS appears with the corresponding Boltzmann probability where the energy is the negative length -l of the IS. For T 0, only ground states, i.e., the longest IS (LIS), contribute, also called Ulam's problem. We introduce an algorithm which allows us to directly sample ISs in perfect equilibrium in polynomial time, for any given sequence and any temperature. Thus, we can study very large sizes. We obtain averages for the first and second moments of the number of ISs as functions of n and confirm analytical predictions. Furthermore, we analyze for low temperature T the sampled ISs by computing the distribution of overlaps and performing hierarchical cluster analyses. In the thermodynamic limit n oo the distribution of overlaps stays broad and the configuration landscape remains complex. Thus, Ulam's problem exhibits replica symmetry breaking (RSB). This means it constitutes a model with complex equilibrium behavior which can be studied numerically exactly in a highly efficient way. This is in contrast to other models, where RSB becomes exponentially irrelevant for the equilibrium behavior in the thermodynamic limit, such as in a random exclusive-or satisfiability (XORSAT) problem, or models where RSB remains relevant, such as spin glasses or NP-hard optimization problems, but where no fast exact algorithms are known.

Automated summary

We study increasing subsequences (ISs) in an ensemble of sequences generated by a permutation of numbers {1, 2, ..., n}. By considering a Boltzmann ensemble at temperature T, we are able to analyze the equilibrium behavior of ISs and explore the effects of temperature on the distribution of overlaps and the complexity of the configuration landscape. We introduce an algorithm that allows us to sample ISs accurately and efficiently, enabling us to study large-scale systems and confirm theoretical predictions.