Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons

DOI10.1016/J.AIM.2023.109480MaRDI QIDQ6201178zbMATH OpenOpenAlexWikidataFDO

Authors Jacopo Borga, William da Silva, Ewain Gwynne

Publication date 20 February 2024

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Brownian excursionfragmentation processlongest increasing subsequencesBrownian permutonBrownian cographonlargest homogeneous sets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Continuous-time Markov processes on general state spaces (60J25) Combinatorial probability (60C05)

Abstract: The Brownian separable permutons are a one-parameter family -- indexed by $pin(0,1)$ -- of universal limits of random constrained permutations. We show that for each $pin(0,1)$, there are explicit constants $$ such that the length of the longest increasing subsequence in a random permutation of size $n$ sampled from the Brownian separable permuton is between $n^{alph{a}_{\ast }(p)-o(1)}$ and $$ with probability tending to 1 as $noinfty$. In the symmetric case $p=1/2$, we have $alph{a}_{\ast }(p)approx0.812$ and $$. We present numerical simulations which suggest that the lower bound $alph{a}_{\ast }(p)$ is close to optimal in the whole range $pin(0,1)$. Our results work equally well for the closely related Brownian cographons. In this setting, we show that for each $pin(0,1)$, the size of the largest clique (resp. independent set) in a random graph on $n$ vertices sampled from the Brownian cographon is between $n^{alph{a}_{\ast }(p)-o(1)}$ and $$ (resp. $n^{alph{a}_{\ast }(1-p)-o(1)}$ and $$) with probability tending to 1 as $noinfty$. Our proofs are based on the analysis of a fragmentation process embedded in a Brownian excursion introduced by Bertoin (2002). We expect that our techniques can be extended to prove similar bounds for uniform separable permutations and uniform cographs.

Recommendations

• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• The Brownian limit of separable permutations
• On the Brownian separable permuton
• The permuton limit of random recursive separable permutations
• Locally uniform random permutations with large increasing subsequences

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 918811 (Why is no real title available?)
• A decorated tree approach to random permutations in substitution-closed classes
• A mating-of-trees approach for graph distances in random planar maps
• A variational problem for random Young tableaux
• Almost all \(H\)-free graphs have the Erdős-Hajnal property
• An approximation of partial sums of independent RV'-s, and the sample DF. I
• Brownian motion. With an appendix by Oded Schramm and Wendelin Werner
• Conditioning subordinators embedded in Markov processes
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Fluctuations of Lévy processes with applications. Introductory lectures
• Graphon convergence of random cographs
• Hammersley's interacting particle process and longest increasing subsequences
• How fast planar maps get swallowed by a peeling process
• Large networks and graph limits
• Lengths of monotone subsequences in a Mallows permutation
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Limiting curves for i.i.d. records
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Longest increasing subsequences in pattern-restricted permutations
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• Monotonous subsequences and the descent process of invariant random permutations
• Multidimensional version of the results of Komlos, Major and Tusnady for vectors with finite exponential moments
• On Increasing Subsequences of I.I.D. Samples
• On the Brownian separable permuton
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Phase uniqueness for the Mallows measure on permutations
• Ramsey-type theorems
• Random Fragmentation and Coagulation Processes
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Renewal theory and level passage by subordinators
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Scaling limits of permutation classes with a finite specification: a dichotomy
• Self-similar fragmentations
• Superlogarithmic cliques in dense inhomogeneous random graphs
• The Brownian limit of separable permutations
• The Erdős-Hajnal conjecture. A survey
• The length of the longest increasing subsequence of a random Mallows permutation
• The permuton limit of strong-Baxter and semi-Baxter permutations is the skew Brownian permuton
• The skew Brownian permuton: A new universality class for random constrained permutations
• The standard additive coalescent
• The surprising mathematics of longest increasing subsequences
• Thermodynamic limit for the Mallows model on \(S_n\)
• Universal limits of substitution-closed permutation classes

Cited in

(1)

• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

This page was built for publication: Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons

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