Locally uniform random permutations with large increasing subsequences

DOI10.5070/C63362784MaRDI QIDQ6204686zbMATH OpenOpenAlexFDO

Authors

Publication date 2 April 2024

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.07658

zbMATH Keywords

random permutationslongest increasing subsequencespermutons

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among $N$ uniformly random points on $[0,1{]}^2$ has size asymptotically $2sqrtN$. More generally, the order $Theta(sqrtN)$ still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of $N$ greater than $sqrtN$, up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.

Recommendations

• Monotone subsequences in locally uniform random permutations
• On increasing subsequences of random permutations
• On the distribution of the length of the longest increasing subsequence of random permutations
• Increasing sequences of independent points on the planar lattice
• On Increasing Subsequences of I.I.D. Samples

Cites work

• A concentration bound for the longest increasing subsequence of a randomly chosen involution
• Cliques in dense inhomogeneous random graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• Finitely forcible graphons and permutons
• Fixed points and cycle structure of random permutations
• Hammersley's interacting particle process and longest increasing subsequences
• Lengths of monotone subsequences in a Mallows permutation
• Limiting curves for i.i.d. records
• Limits of permutation sequences
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Monotone subsequences in locally uniform random permutations
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the length of the longest monotone subsequence in a random permutation
• Probability Inequalities for the Sum of Independent Random Variables
• Quasirandom permutations are characterized by 4-point densities
• Scaling limits of permutation classes with a finite specification: a dichotomy
• Superlogarithmic cliques in dense inhomogeneous random graphs
• The Brownian limit of separable permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• The surprising mathematics of longest increasing subsequences
• Universal limits of substitution-closed permutation classes
• Weighted sums of certain dependent random variables

Cited in

(6)

• Continuity of limit surfaces of locally uniform random permutations
• Binary search trees of permuton samples
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• Binary search trees of permuton samples
• Monotone subsequences in locally uniform random permutations
• Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons

This page was built for publication: Locally uniform random permutations with large increasing subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204686)