From Hammersley's lines to Hammersley's trees (Q1647922): Difference between revisions

The paper is devoted to Ulam's problem of estimating the length \(l(\sigma)\) of the longest decreasing sub-sequence of \(\sigma,\) where \(\sigma\) is a given permutation of \(\{1,2,\dots,n\},\) when the permutation of \(\{1,2,\dots,n\}\) is sampled uniformly among all permutations of \(\{1,2,\dots,n\}.\) The main result of the paper is the following one: if \(\mathbb R(\sigma)\) is a set of increasing stacks/heaps, then for every distribution \(\mu\) on \(\mathbb N=\{1,2,\dots,n\}\) which is not the Dirac mass at 1 there exists a constant \(c_{\mu}\in (1,+\infty)\) such that \[ E[\mathbb R(n)]\equiv c_{\mu}\log(n). \] This result is a generalization of a result by \textit{G. Istrate} and \textit{C. Bonchiş} [Lect. Notes Comput. Sci. 9133, 261--271 (2015; Zbl 1432.68326)] allowing the heaps to be random Galton-Watson trees without leaves.