From Hammersley's lines to Hammersley's trees (Q1647922): Difference between revisions
From MaRDI portal
Latest revision as of 01:32, 16 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | From Hammersley's lines to Hammersley's trees |
scientific article |
Statements
From Hammersley's lines to Hammersley's trees (English)
0 references
27 June 2018
0 references
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.
0 references
Hammersley process
0 references
heap sorting
0 references
patience sorting
0 references
longest increasing subsequences
0 references
interacting particles systems
0 references
0 references
0 references
0 references