Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

Budzinski, Thomas; Sénizergues, Delphin

Journal de l’École polytechnique — Mathématiques, Tome 11 (2024), pp. 395-430

We prove that the size of the largest common subtree between two uniform, independent, leaf-labeled random binary trees of size $n$ is typically less than $n^{1/2-\epsilon }$ for some $\epsilon >0$. Our proof relies on the coupling between discrete random trees and the Brownian tree and on a recursive decomposition of the Brownian tree due to Aldous. Along the way, we also show that almost surely, there is no $(1-\epsilon )$-Hölder homeomorphism between two independent copies of the Brownian tree.

Nous montrons que la taille du plus grand sous-arbre commun entre deux arbres binaires étiquetés de taille $n$ choisis uniformément et indépendamment est plus petite que $n^{1/2-\epsilon }$ pour un certain $\epsilon >0$. La preuve repose sur le couplage entre les arbres aléatoires discrets et l’arbre brownien ainsi que sur une décomposition récursive de l’arbre brownien introduite par Aldous. En chemin, nous montrons également que presque sûrement, il n’existe pas d’homéomorphisme $(1-\epsilon )$-höldérien entre deux arbres browniens indépendants.

Classification : 60C05, 05C80
Keywords: Maximum agreement subtree, Brownian tree, Hölder equivalence
Mots-clés : Plus grand sous-arbre commun, arbre brownien, équivalence höldérienne

[1] Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina Critical random graphs: limiting constructions and distributional properties, Electron. J. Probab., Volume 15 (2010), pp. 741-775 | DOI | MR | Zbl

[2] Aldous, David The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1 - 28 | DOI | MR | Zbl

[3] Aldous, David The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248 - 289 | DOI | MR | Zbl

[4] Aldous, David Recursive self-similarity for random trees, random triangulations and Brownian excursion, Ann. Probab., Volume 22 (1994) no. 2, pp. 527-545 | DOI | MR | Zbl

[5] Aldous, David On the largest common subtree of random leaf-labeled binary trees, SIAM J. Discrete Math., Volume 36 (2022) no. 1, pp. 299-314 | MR | Zbl | DOI

[6] Bassino, F.; Bouvel, M.; Drmota, M.; Féray, V.; Gerin, L.; Maazoun, M.; Pierrot, A. Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, Combin. Theory, Volume 2 (2022) no. 3, 15, 35 pages | MR | Zbl | DOI

[7] Bernstein, Daniel Irving; Ho, Lam Si Tung; Long, Colby; Steel, Mike; John, Katherine St.; Sullivant, Seth Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math., Volume 29 (2015) no. 4, pp. 2065-2074 | MR | Zbl | DOI

[8] Bonk, Mario; Tran, Huy The continuum self-similar tree, Fractal geometry and stochastics VI (Freiberg, Uta; Hambly, Ben; Hinz, Michael; Winter, Steffen, eds.), Springer International Publishing, Cham, 2021, pp. 143-189 | Zbl | DOI

[9] Borga, Jacopo; Da Silva, William; Gwynne, Ewain Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons, Adv. Math., Volume 439 (2024), 109480 | DOI | MR

[10] Bryant, David; McKenzie, Andy; Steel, Mike The size of a maximum agreement subtree for random binary trees, Bioconsensus. DIMACS working group meetings on bioconsensus, October 25–26, 2000 and October 2–5, 2001, DIMACS Center, American Mathematical Society, Providence, RI, 2003, pp. 55-65 | Zbl | MR

[11] Burago, Dmitri; Burago, Yuri; Ivanov, Sergei A course in metric geometry, Graduate Studies in Math., 33, American Mathematical Society, Providence, RI, 2001 | DOI | MR

[12] Croydon, David; Hambly, Ben Self-similarity and spectral asymptotics for the continuum random tree, Stochastic Processes Appl., Volume 118 (2008) no. 5, pp. 730-754 | MR | DOI | Zbl

[13] Dufresne, Daniel Algebraic properties of beta and gamma distributions, and applications, Adv. in Appl. Math., Volume 20 (1998) no. 3, pp. 285-299 | DOI | MR | Zbl

[14] Finden, C. R.; Gordon, A. D. Obtaining common pruned trees, J. Classification, Volume 2 (1985) no. 1, pp. 255-276 | DOI

[15] Gordon, A. D. On the assessment and comparison of classifications, Analyse de Données et Informatique (1980), p. 149–160 | Zbl

[16] Gromov, Mikhael Carnot-Carathéodory spaces seen from within, Sub-Riemannian geometry (Bellaïche, André; Risler, Jean-Jacques, eds.) (Progress in Math.), Birkhäuser Basel, Basel, 1996, pp. 79-323 | DOI | Zbl

[17] Gwynne, Ewain; Miller, Jason Existence and uniqueness of the Liouville quantum gravity metric for $\gamma \in (0,2)$, Invent. Math., Volume 223 (2021) no. 1, pp. 213-333 | DOI | MR | Zbl

[18] Kennedy, Douglas P. The distribution of the maximum Brownian excursion, J. Appl. Probability, Volume 13 (1976) no. 2, pp. 371-376 | DOI | MR | Zbl

[19] Khezeli, Ali An improved lower bound on the largest common subtree of random leaf-labeled binary trees, 2022 | arXiv

[20] Kubicka, Ewa; Kubicki, Grzegorz; McMorris, FR On agreement subtrees of two binary trees, Congr. Numer., Volume 88 (1992), p. 217-217 | MR | Zbl

[21] Le Gall, Jean-François Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | Zbl | MR

[22] Le Gall, Jean-François Uniqueness and universality of the Brownian map, Ann. Probab., Volume 41 (2013), pp. 2880-2960 | MR | Zbl

[23] Markin, Alexey On the extremal maximum agreement subtree problem, Discrete Appl. Math., Volume 285 (2020), pp. 612-620 | DOI | MR | Zbl

[24] Miermont, Grégory The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math., Volume 210 (2013) no. 2, pp. 319-401 | DOI | MR | Zbl

[25] Misra, Pratik; Sullivant, Seth Bounds on the expected size of the maximum agreement subtree for a given tree shape, SIAM J. Discrete Math., Volume 33 (2019) no. 4, pp. 2316-2325 | DOI | MR | Zbl

[26] Pitman, J. Combinatorial stochastic processes, Lect. Notes in Math., 1875, Springer-Verlag, Berlin, 2006 | MR

[27] Pittel, Boris Expected number of induced subtrees shared by two independent copies of a random tree, SIAM J. Discrete Math., Volume 37 (2023) no. 1, pp. 1-16 | DOI | MR | Zbl

[28] Rémy, Jean-Luc Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., Volume 19 (1985) no. 2, pp. 179-195 | DOI | Numdam | Zbl | MR

[29] Steel, Mike; Warnow, Tandy Kaikoura tree theorems: Computing the maximum agreement subtree, Inform. Process. Lett., Volume 48 (1993) no. 2, pp. 77-82 | DOI | MR | Zbl