Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem

DOI10.1090/S0273-0979-99-00796-XzbMath0937.60001WikidataQ29038006 ScholiaQ29038006MaRDI QIDQ4269106

David J. Aldous, Persi Diaconis

Publication date: 31 October 1999

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial aspects of representation theory (05E10) Interacting particle systems in time-dependent statistical mechanics (82C22) Combinatorial probability (60C05) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Random matrices (algebraic aspects) (15B52)

Related Items

Ulam's problem and Hammersley's process, The symmetry in the martingale inequality, Order-Invariant Measures on Fixed Causal Sets, Moderate deviations for longest increasing subsequences: The upper tail, Relating random matrix map enumeration to a universal symbol calculus for recurrence operators in terms of Bessel–Appell polynomials, THE KARDAR–PARISI–ZHANG EQUATION AND UNIVERSALITY CLASS, A limit theorem for shifted Schur measures, Longest increasing subsequences in sliding windows, Enumerating longest increasing subsequences and patience sorting, When the law of large numbers fails for increasing subsequences of random permutations, Maxima of log-correlated fields: some recent developments*, Bounds on the Expected Size of the Maximum Agreement Subtree, Lyndon array construction during Burrows-Wheeler inversion, Variations on Hammersley’s interacting particle process, Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture, On the longest increasing subsequence of a circular list, Hammersley's interacting particle process and longest increasing subsequences, Dynamic programming and board games: a survey, From Hammersley's lines to Hammersley's trees, Limit shapes for random square Young tableaux, RIGHT TAIL ASYMPTOTIC EXPANSION OF TRACY–WIDOM BETA LAWS, The Pearcey process, Stein’s method and Plancherel measure of the symmetric group, Heavy tails in last-passage percolation, Commentary on “Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem” by David Aldous and Persi Diaconis, Integrals over classical groups, random permutations, Toda and Toeplitz lattices, Longest monotone subsequences and rare regions of pattern-avoiding permutations, Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process, The random average process and random walk in a space-time random environment in one dimension, On the monotonicity of a data stream, Space-Efficient Algorithms for Longest Increasing Subsequence, A KPZ cocktail-shaken, not stirred\dots: Toasting 30 years of kinetically roughened surfaces, Longest increasing subsequences and log concavity, Unnamed Item, A central limit theorem for the length of the longest common subsequences in random words, Limiting shapes of birth-and-death processes on Young diagrams, On the largest Kronecker and Littlewood-Richardson coefficients, Stein's method and random character ratios, Finite size corrections relating to distributions of the length of longest increasing subsequences, Non-intersecting Brownian walkers and Yang-Mills theory on the sphere, Random partial orders defined by angular domains, The Preisach graph and longest increasing subsequences, Empirical scaling of the length of the longest increasing subsequences of random walks, Discrete gap probabilities and discrete Painlevé equations., Letter change bias and local uniqueness in optimal sequence alignments, Brownian motion, Chern-Simons theory, and 2d Yang-Mills, Integrals over Grassmannians and random permutations., Tropical combinatorics and Whittaker functions, Airplane boarding meets express line queues, The distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets, Faster algorithms for computing longest common increasing subsequences, The monoids of the patience sorting algorithm, Expected lengths and distribution functions for Young diagrams in the hook, Random matrix central limit theorems for nonintersecting random walks, Rare events in stochastic partial differential equations on large spatial domains, A simple derivation of the Tracy–Widom distribution of the maximal eigenvalue of a Gaussian unitary random matrix, Optimal online selection of a monotone subsequence: a central limit theorem, Average case analysis of disk scheduling, increasing subsequences and spacetime geometry, Precise asymptotics for random matrices and random growth models, Comparing bacterial genomes from linear orders of patterns, Space-efficient algorithms for longest increasing subsequence, LIL for the length of the longest increasing subsequences, GENERALIZED RANDOM MATRIX THEORY: A MATHEMATICAL PROBE FOR COMPLEXITY, A probabilistic interpretation of the Macdonald polynomials, Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Random matrix theory over finite fields, The matching, birthday and the strong birthday problem: a contemporary review, Stein's method, Jack measure, and the Metropolis algorithm, A geometric form for the extended patience sorting algorithm, A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length, A concentration bound for the longest increasing subsequence of a randomly chosen involution, Counting formulas associated with some random matrix averages, Hammersley's process with sources and sinks, Longest convex chains, Asymptotics of Plancherel measures for symmetric groups, The BRS-inequality and its applications, On the distribution of the length of the longest increasing subsequence in a random permutation, Finding and counting permutations via CSPs, Spatial random permutations and infinite cycles, Geometric RSK correspondence, Whittaker functions and symmetrized random polymers, Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences, On the topology of complexes of injective words, Quickest online selection of an increasing subsequence of specified size, The Hopf algebra of uniform block permutations., Combinatorics of patience sorting monoids, Zero Biasing and Jack Measures, The eigenvalue distribution of a random unipotent matrix in its representation on lines, On-line scheduling with monotone subsequence constraints, Random matrix theory and its applications, The ghost-box-ball system: a unified perspective on soliton cellular automata, the RSK algorithm and phase shifts, Periodic Pólya urns, the density method and asymptotics of Young tableaux, Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting, Expected length of the longest common subsequence for large alphabets, A conversation with David J. Aldous, On the distribution of the largest eigenvalue in principal components analysis, Optimal rules for the sequential selection of monotone subsequences of maximum expected length, Lengths of monotone subsequences in a Mallows permutation, Multi-state asymmetric simple exclusion processes, Fast and longest rollercoasters, Hydrodynamical methods for analyzing longest increasing subsequences, Unnamed Item, Harold Widom’s work in random matrix theory, Linear algebra and multivariate analysis in statistics: development and interconnections in the twentieth century, An asymptotically optimal algorithm for online stacking, KPZ limit theorems, Asymptotic expansions relating to the distribution of the length of longest increasing subsequences, Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays, Unnamed Item, Large deviations-based upper bounds on the expected relative length of longest common subsequences, Estimating the Longest Increasing Sequence in Polylogarithmic Time, Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment, Statistical self-similarity of one-dimensional growth processes, Unnamed Item, Optimal boarding policies for thin passengers, Longest increasing subsequence under persistent comparison errors, Hydrodynamic limit for an evolutional model of two-dimensional Young diagrams, A matrix model for plane partitions, Unnamed Item, Martingales and character ratios, All order asymptotic expansion of large partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the speed of convergence in first-passage percolation
• Markov chains and stochastic stability
• Descending subsequences of random permutations
• Symmetric functions and P-recursiveness
• Oriented percolation in two dimensions
• Mathematical problems and games
• On computing the length of longest increasing subsequences
• A variational problem for random Young tableaux
• Longest increasing subsequences of random colored permutations
• Level-spacing distributions and the Airy kernel
• Increasing subsequences and the classical groups
• On the distribution of the length of the second row of a Young diagram under Plancherel measure
• Sequence comparison significance and Poisson approximation
• Algebraic aspects of increasing subsequences
• Hammersley's interacting particle process and longest increasing subsequences
• On increasing subsequences of random permutations
• Shape fluctuations and random matrices
• Longest Increasing and Decreasing Subsequences
• Non-equilibrium behaviour of a many particle process: Density profile and local equilibria
• On the distribution of the length of the longest increasing subsequence of random permutations
• Poissonian approximation for the tagged particle in asymmetric simple exclusion
• Asymptotics of Plancherel measures for symmetric groups
• On the distributions of the lengths of the longest monotone subsequences in random words