Nous montrons que la taille du plus grand sous-arbre commun entre deux arbres binaires étiquetés de taille choisis uniformément et indépendamment est plus petite que pour un certain . 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 -höldérien entre deux arbres browniens indépendants.
We prove that the size of the largest common subtree between two uniform, independent, leaf-labeled random binary trees of size is typically less than for some . 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 -Hölder homeomorphism between two independent copies of the Brownian tree.
CC-BY 4.0
@article{JEP_2024__11__395_0,
author = {Thomas Budzinski and Delphin S\'enizergues},
title = {Maximum agreement subtrees and {H\"older} homeomorphisms between {Brownian} trees},
journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
pages = {395--430},
publisher = {\'Ecole polytechnique},
volume = {11},
year = {2024},
doi = {10.5802/jep.256},
language = {en},
url = {https://jep.centre-mersenne.org/articles/10.5802/jep.256/}
}
TY - JOUR AU - Thomas Budzinski AU - Delphin Sénizergues TI - Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees JO - Journal de l’École polytechnique — Mathématiques PY - 2024 SP - 395 EP - 430 VL - 11 PB - École polytechnique UR - https://jep.centre-mersenne.org/articles/10.5802/jep.256/ DO - 10.5802/jep.256 LA - en ID - JEP_2024__11__395_0 ER -
%0 Journal Article %A Thomas Budzinski %A Delphin Sénizergues %T Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees %J Journal de l’École polytechnique — Mathématiques %D 2024 %P 395-430 %V 11 %I École polytechnique %U https://jep.centre-mersenne.org/articles/10.5802/jep.256/ %R 10.5802/jep.256 %G en %F JEP_2024__11__395_0
Thomas Budzinski; Delphin Sénizergues. Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees. Journal de l’École polytechnique — Mathématiques, Tome 11 (2024), pp. 395-430. doi : 10.5802/jep.256. https://jep.centre-mersenne.org/articles/10.5802/jep.256/
[1] - “Critical random graphs: limiting constructions and distributional properties”, Electron. J. Probab. 15 (2010), p. 741-775 | DOI | MR | Zbl
[2] - “The continuum random tree. I”, Ann. Probab. 19 (1991) no. 1, p. 1 - 28 | DOI | MR | Zbl
[3] - “The continuum random tree. III”, Ann. Probab. 21 (1993) no. 1, p. 248 - 289 | DOI | MR | Zbl
[4] - “Recursive self-similarity for random trees, random triangulations and Brownian excursion”, Ann. Probab. 22 (1994) no. 2, p. 527-545 | DOI | MR | Zbl
[5] - “On the largest common subtree of random leaf-labeled binary trees”, SIAM J. Discrete Math. 36 (2022) no. 1, p. 299-314 | DOI | MR | Zbl
[6] - “Linear-sized independent sets in random cographs and increasing subsequences in separable permutations”, Combin. Theory 2 (2022) no. 3, article ID 15, 35 pages | DOI | MR | Zbl
[7] - “Bounds on the expected size of the maximum agreement subtree”, SIAM J. Discrete Math. 29 (2015) no. 4, p. 2065-2074 | DOI | MR | Zbl
[8] - “The continuum self-similar tree”, in Fractal geometry and stochastics VI (U. Freiberg, B. Hambly, M. Hinz & S. Winter, eds.), Springer International Publishing, Cham, 2021, p. 143-189 | DOI | Zbl
[9] - “Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons”, Adv. Math. 439 (2024), article ID 109480 | DOI | MR
[10] - “The size of a maximum agreement subtree for random binary trees”, in Bioconsensus. DIMACS working group meetings on bioconsensus, October 25–26, 2000 and October 2–5, 2001, DIMACS Center, American Mathematical Society, Providence, RI, 2003, p. 55-65 | Zbl
[11] - A course in metric geometry, Graduate Studies in Math., vol. 33, American Mathematical Society, Providence, RI, 2001 | DOI
[12] - “Self-similarity and spectral asymptotics for the continuum random tree”, Stochastic Processes Appl. 118 (2008) no. 5, p. 730-754 | DOI | MR | Zbl
[13] - “Algebraic properties of beta and gamma distributions, and applications”, Adv. in Appl. Math. 20 (1998) no. 3, p. 285-299 | DOI | MR | Zbl
[14] - “Obtaining common pruned trees”, J. Classification 2 (1985) no. 1, p. 255-276 | DOI
[15] - “On the assessment and comparison of classifications”, Analyse de Données et Informatique (1980), p. 149–160 | Zbl
[16] - “Carnot-Carathéodory spaces seen from within”, in Sub-Riemannian geometry (A. Bellaïche & J.-J. Risler, eds.), Progress in Math., Birkhäuser Basel, Basel, 1996, p. 79-323 | DOI | Zbl
[17] - “Existence and uniqueness of the Liouville quantum gravity metric for ”, Invent. Math. 223 (2021) no. 1, p. 213-333 | DOI | MR | Zbl
[18] - “The distribution of the maximum Brownian excursion”, J. Appl. Probability 13 (1976) no. 2, p. 371-376 | DOI | MR | Zbl
[19] - “An improved lower bound on the largest common subtree of random leaf-labeled binary trees”, 2022 | arXiv
[20] - “On agreement subtrees of two binary trees”, Congr. Numer. 88 (1992), p. 217-217 | MR | Zbl
[21] - “Random trees and applications”, Probab. Surv. 2 (2005), p. 245-311 | DOI | MR | Zbl
[22] - “Uniqueness and universality of the Brownian map”, Ann. Probab. 41 (2013), p. 2880-2960 | MR | Zbl
[23] - “On the extremal maximum agreement subtree problem”, Discrete Appl. Math. 285 (2020), p. 612-620 | DOI | MR | Zbl
[24] - “The Brownian map is the scaling limit of uniform random plane quadrangulations”, Acta Math. 210 (2013) no. 2, p. 319-401 | DOI | MR | Zbl
[25] - “Bounds on the expected size of the maximum agreement subtree for a given tree shape”, SIAM J. Discrete Math. 33 (2019) no. 4, p. 2316-2325 | DOI | MR | Zbl
[26] - Combinatorial stochastic processes, Lect. Notes in Math., vol. 1875, Springer-Verlag, Berlin, 2006
[27] - “Expected number of induced subtrees shared by two independent copies of a random tree”, SIAM J. Discrete Math. 37 (2023) no. 1, p. 1-16 | DOI | MR | Zbl
[28] - “Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire”, RAIRO Inform. Théor. 19 (1985) no. 2, p. 179-195 | DOI | Numdam | Zbl
[29] - “Kaikoura tree theorems: Computing the maximum agreement subtree”, Inform. Process. Lett. 48 (1993) no. 2, p. 77-82 | DOI | MR | Zbl
Cité par Sources :