The longest increasing subsequence of random separable permutations (Thomas Budzinski, ENS Lyon)

31.03.2025 16:15 – 18:00

Consider a binary tree $T$ (i.e. with vertex degrees $1$ or $3$) decorated with positive or negative signs on its internal nodes. We are interested in the size of the largest subtree of $T$ where no negative node has degree 3. When $T$ is uniform among binary trees with size $n$ and the signs are i.i.d. Bernoulli with parameter $p$, this also describes the length of the longest increasing subsequence in natural models of random separable permutations.
We will see that this quantity behaves like $n^{\alpha(p)+o(1)}$, where $\alpha(p)$ solves the following nice equation: \[ \frac{2^{1/\alpha}\sqrt{\pi}\,\Gamma(1- /(2\alpha))}{\Gamma(1/2-1/(2\alpha))}=\frac{p-1}{p}. \]
Based on ongoing work with Arka Adhikari, Jacopo Borga, William da Silva and Delphin Sénizergues

Lieu

Conseil Général 7-9, Room 1-15, Séminaire Math Physics

entrée libre