Universal lower bound conjecture for binary search tree height of permuton samples

Let $cmathcal{P}^n_\mu$ be a sample of $n$ points from a permuton $cmu$, and let $cmathcal{T}\langle\mathcal{P}^n_\mu\rangle$ be the corresponding binary search tree, with height denoted by $h(\mathcal{T}\langle\mathcal{P}^n_\mu\rangle)$. Let $c^*$ be the unique solution with $c\geq 2$ of

$$c\log(2e/c)=1.$$

Universal height lower-bound conjecture. For any permuton $cmu$ and $cvarepsilon>0$,

$$\lim_{n\to\infty}\mathbb{P}\left[\frac{h\left(\mathcal{T}\langle\mathcal{P}^n_\mu\rangle\right)}{\log n}<c^*-\varepsilon\right]=0.$$

The conjecture asserts that the uniform-permuton constant $c^*$ is a universal lower bound for the typical logarithmic height of binary search trees built from permuton samples, even when the hypotheses of the proved universality theorem fail. The paper notes that no permuton with asymptotically smaller height and non-vanishing probability is known, while examples show that the height can be larger than $c^*\log n$.