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

DOI10.1016/J.AIM.2023.109480arXiv2303.17030OpenAlexW4390880361WikidataQ130072498 ScholiaQ130072498MaRDI QIDQ6201178FDOQ6201178

Authors: Jacopo Borga, William da Silva, Ewain Gwynne 

Publication date: 20 February 2024

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

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}_{*}(p)-o(1)}$ and $$ with probability tending to 1 as $noinfty$. In the symmetric case $p=1/2$, we have $alph{a}_{*}(p)approx0.812$ and $$. We present numerical simulations which suggest that the lower bound $alph{a}_{*}(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}_{*}(p)-o(1)}$ and $$ (resp. $n^{alph{a}_{*}(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.

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)

Cites Work

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

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)