Longest increasing subsequences of dyadic-type chaotic orbits

Abstract

This paper studies the longest increasing subsequence (LIS) problem for sequences generated by dyadic-type chaotic interval maps. Starting from a single point $x\in [0,1)$ chosen uniformly at random, we form the order pattern of the first $N$ points of its orbit, with the doubling map as the basic model. Let ${\lambda }_1^{(N)}$ be the LIS length, equivalently the length of the first row of the Young diagram obtained by Schensted's insertion. We show that $\mathbb{E}[{\lambda }_1^{(N)}]/\sqrt{N}\to 2$, matching the leading asymptotics in the classical Ulam--Hammersley problem for uniform random permutations.

28 pages, 3 figures