The longest increasing subsequence of Brownian separable permutons

Abstract

We establish a scaling limit result for the length $\mathrm{LIS}(\ddot{I}{ƒ}_n)$ of the longest increasing subsequence of a permutation $\ddot{I}{ƒ}_n$ of size $n$ sampled from the Brownian separable permuton $\hat{\mathbf{I}}{¼}_p$ of parameter $p\in (0,1)$, which is the universal limit of pattern-avoiding permutations. Specifically, we prove that \[\frac{\operatorname{LIS}(σ_n)}{n^α}\;\underset{n\to\infty}{\overset{\mathrm{a.s.}}{\longrightarrow}}\; X,\] where $\hat{I}\pm =\hat{I}\pm (p)$ is the unique solution in the interval $(1/2,1)$ to the equation \[\frac{1}{4^{\frac{1}{2α}}\sqrtπ}\,\frac{Γ\big(\tfrac{1}{2}-\tfrac{1}{2α}\big)}{Γ\big(1-\tfrac{1}{2α}\big)}=\frac{p}{p-1},\] and $X=X(p)$ is a non-deterministic and a.s. positive and finite random variable, which is a measurable function of the Brownian separable permuton. Notably, the exponent $\hat{I}\pm (p)$ is an increasing continuous function of $p$ with $\hat{I}\pm (0^{+})=1/2$, $\hat{I}\pm (1^{-})=1$ and $\hat{I}\pm (1/2)\approx 0.815226$, which corresponds to the permuton limit of uniform separable permutations. We prove analogous results for the size of the largest clique of a graph sampled from the Brownian cographon of parameter $p\in (0,1)$.

Comments are welcome!