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

The Brownian separable permutons are a one-parameter family – indexed by $p\in (0,1)$ – of universal limits of random constrained permutations. We show that for each $p\in (0,1)$, there are explicit constants $1\mathrm{/}2<{\alpha }_{\ast }(p)\le {\beta }^{\ast }(p)<1$ 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^{{\alpha }_{\ast }(p)-o(1)}$ and $n^{{\beta }^{\ast }(p)+o(1)}$ with probability tending to 1 as $n\to \mathrm{\infty }$. In the symmetric case $p=1\mathrm{/}2$, we have ${\alpha }_{\ast }(p)\approx 0.812$ and ${\beta }^{\ast }(p)\approx 0.975$. We present numerical simulations which suggest that the lower bound ${\alpha }_{\ast }(p)$ is close to optimal in the whole range $p\in (0,1)$. Our results work equally well for the closely related Brownian cographons. In this setting, we show that for each $p\in (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^{{\alpha }_{\ast }(p)-o(1)}$ and $n^{{\beta }^{\ast }(p)+o(1)}$ (resp. $n^{{\alpha }_{\ast }(1-p)-o(1)}$ and $n^{{\beta }^{\ast }(1-p)+o(1)}$) with probability tending to 1 as $n\to \mathrm{\infty }$. 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.