Regensburg 2022 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

DY: Fachverband Dynamik und Statistische Physik

DY 26: Critical Phenomena and Phase Transitions

DY 26.7: Vortrag

Mittwoch, 7. September 2022, 11:30–11:45, H20

Replica-Symmetry Breaking for Ulam’s problem — •Phil Krabbe¹, Hendrik Schawe², and Alexander K. Hartmann¹ — ¹Institute of Physics, University of Oldenburg, Germany — ²LPTM, CY Cergy Paris Université, France

For a given sequence X=x₁,x₂,…, x_n of numbers, an increasing subsequence (IS) is a subset of l elements i(1)<i(2)<… <i(l) such that x_i(1)<x_i(2) < … < x_i(l). The longest increasing subsequences (LIS) problem, i.e. to maximise l, was considered numerically first by S. Ulam and is a well studied topic. Here we consider the length l as an energy and study the canonical ensemble of ISs controlled by temperature parameter T, which includes the LIS for T→ 0. We extended our algorithm from [1] such that we can draw ISs in perfect equilibrium in polynomial time. This allows us to study large sequences with up to n=8192 numbers.

We studied the IS numerically [2] for sequences X being permutations of integers. As measurable quantities, we analysed the mean energy, the specific heat C and and the overlap q between the drawn ISs. Our exact-sampling results indicate that the IS exhibits in the thermodynamic limit a complex energy landscape in the spirit of Replica Symmetry Breaking, characterised by a broad distribution P(q) of overlaps and a hierarchical organization of the configuration space.

[1] P. Krabbe, H. Schawe and A.K. Hartmann, Phys. Rev. E 101, 062109 (2020)

[2] A.K. Hartmann, Big Practical Guide to Computer Simulations, World Scientific (2015)