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/2 < \alpha_∗(p) \leq \beta^∗(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_∗(p)−o(1)}\) and \(n^{\beta^∗(p)+o(1)}\) with probability tending to 1 as \(n \to \infty\). In the symmetric case \(p = 1/2\), we have \(\alpha_∗(p) \approx 0.812\) and \(β^∗(p) \approx 0.975\). We present numerical simulations which suggest that the lower bound \(\alpha_∗(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 is between \(n^{\alpha_∗(p)−o(1)}\) and \(n^{\beta^∗(p)+o(1)}\) (resp. \(n^{\alpha_∗(1-p)−o(1)}\) and \(n^{\beta^∗(1-p)+o(1)}\) ) with probability tending to 1 as \(n \to \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.