Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 40 min ago
PreprintCC BY-SA 4.0arXiv

Longest increasing subsequences of dyadic-type chaotic orbits

  • Shinsuke Iwao
  • Fumihiko Nakamura
  • Yushi Nakano
Open at sourcePDFDOICite

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∈[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 λ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 𝔼[λ1(N)]/√N→ 2, matching the leading asymptotics in the classical Ulam--Hammersley problem for uniform random permutations.

Related

  1. The longest increasing subsequences of Luce permutations and permutons
    Jacopo Borga, Victor Dubach
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityHALarXiv
  2. Recurrences for permutations with long increasing subsequences
    Manuel Kauers, Chen Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Log-concavity of longest increasing subsequence
    Yupeng Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. On Chen's conjecture for the log-concavity of the longest increasing subsequence distribution
    Ernest X. W. Xia
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Degenerating orbits of the Longest Edge Bisection process
    Karim Adiprasito, Daniel Kalmanovich, Yaar Solomon
    HALPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsDynamical systemsHALarXiv

Cite

BibTeXRIS
BibTeX
@misc{iwao2026longest,
  title = {{Longest increasing subsequences of dyadic-type chaotic orbits}},
  author = {Shinsuke Iwao and Fumihiko Nakamura and Yushi Nakano},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.24575},
  eprint = {2608.24575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.24575},
  note = {CC BY-SA 4.0},
}
RIS
TY  - UNPB
TI  - Longest increasing subsequences of dyadic-type chaotic orbits
AU  - Shinsuke Iwao
AU  - Fumihiko Nakamura
AU  - Yushi Nakano
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2608.24575
UR  - https://arxiv.org/abs/2608.24575
AB  - This paper studies the longest increasing subsequence (LIS) problem for sequences generated by dyadic-type chaotic interval maps. Starting from a single point x∈[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 λ_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 𝔼[λ_1^(N)]/√N→ 2, matching the leading asymptotics in the classical Ulam--Hammersley problem for uniform random permutations.
ER  -