Compacted binary trees, stretched exponential and asymptotic behavior of recurrences | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Compacted binary trees, stretched exponential and asymptotic behavior of recurrences

Appears in collection : ALEA Days 2024 / Journées ALEA 2024

Dans cet exposé, je présente une approche d'énumération asymptotique du type guess-and-check pour certaines récurrences, à travers de l'étude des arbres binaires compactés. Un arbre binaire compacté est un graphe acyclique dirigé qui encode un arbre binaire, où on garde une seule copie pour les sous-arbres identiques. Nous prouvons que le nombre des arbres binaires compactés de taille n est asymptotiquement $\Theta\left(n ! 4^n \exp \left(3 a_1 n^{1 / 3}\right) n^{3 / 4}\right)$, avec $a_1 \sim-2.338$ la plus grande racine de la fonction d'Airy. Typiquement, cette expression asymptotique contient un exponentiel étiré, qui est rare et intéressant dans l'énumération asymptotique. Pour arriver à ce résultat, nous postulons d'abord une récurrence à deux paramètres pour ces nombres, puis nous devinons la forme de l'asymptotique et la démontrons toujours à travers de la récurrence. Je présenterai aussi quelques autres applications, et notre effort à généraliser cette méthode. Travail commun avec Andrew Elvey Price et Michael Wallner. https://igm.univ-mlv.fr/~wfang/

Information about the video

Date of recording 14/03/2024
Date of publication 29/03/2024
Institution CIRM
Licence CC BY NC ND
Language French
Audience Researchers, Graduate Students
Director(s) Guillaume Hennenfent
Format MP4

Citation data

DOI 10.24350/CIRM.V.20150403
Cite this video Fang, Wenjie (14/03/2024). Compacted binary trees, stretched exponential and asymptotic behavior of recurrences. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20150403
URL https://dx.doi.org/10.24350/CIRM.V.20150403

Domain(s)

Combinatorics

Bibliography

PRICE, Andrew Elvey, FANG, Wenjie, et WALLNER, Michael. Compacted binary trees admit a stretched exponential. Journal of Combinatorial Theory, Series A, 2021, vol. 177, p. 105306. - https://doi.org/10.1016/j.jcta.2020.105306

MSC codes

Document(s)

https://www.cirm-math.fr/RepOrga/3048/Slides/compacted-tree-fang-en-compressed.pdf

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback