Skip to Main content Skip to Navigation
Conference papers

The height of the Lyndon tree

Abstract : We consider the set $\mathcal{L}_n<$ of n-letters long Lyndon words on the alphabet $\mathcal{A}=\{0,1\}$. For a random uniform element ${L_n}$ of the set $\mathcal{L}_n$, the binary tree $\mathfrak{L} (L_n)$ obtained by successive standard factorization of $L_n$ and of the factors produced by these factorization is the $\textit{Lyndon tree}$ of $L_n$. We prove that the height $H_n$ of $\mathfrak{L} (L_n)$ satisfies $\lim \limits_n \frac{H_n}{\mathsf{ln}n}=\Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta ≃5.092\dots $). The convergence is the convergence in probability of random variables.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 10:20:07 AM
Last modification on : Saturday, October 16, 2021 - 11:18:03 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:41:02 AM


Publisher files allowed on an open archive




Lucas Mercier, Philippe Chassaing. The height of the Lyndon tree. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.957-968, ⟨10.46298/dmtcs.2357⟩. ⟨hal-01229697⟩



Record views


Files downloads