On the length of the longest monotone subsequence in a random permutation

DOI10.1214/aoap/1177005939zbMath0738.05002OpenAlexW1963811858WikidataQ94767378 ScholiaQ94767378MaRDI QIDQ1176972

Alan M. Frieze

Publication date: 25 June 1992

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177005939

zbMATH Keywords

random permutationmartingale inequality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Related Items (14)

A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting ⋮ Hammersley's interacting particle process and longest increasing subsequences ⋮ Concentration of measure and isoperimetric inequalities in product spaces ⋮ Arithmetic subsequences in a random ordering of an additive set ⋮ Decomposing Random Permutations into Order-Isomorphic Subpermutations ⋮ Locally uniform random permutations with large increasing subsequences ⋮ Random partial orders defined by angular domains ⋮ Connect the dots: how many random points can a regular curve pass through? ⋮ Noncommutative martingale concentration inequalities ⋮ A sharp concentration inequality with applications ⋮ Random \(k\)-dimensional orders: Width and number of linear extensions ⋮ Untangling planar graphs from a specified vertex position-Hard cases ⋮ A concentration bound for the longest increasing subsequence of a randomly chosen involution ⋮ Expected length of the longest common subsequence for large alphabets

This page was built for publication: On the length of the longest monotone subsequence in a random permutation