Dans cet exposé, nous introduirons certaines chaînes de Markov simples, dites “montantes-descendantes”, sur les permutations et les graphes. Une étape de la chaîne consiste à dupliquer un élément aléatoire de la permutation ou un sommet aléatoire du graphe (pas montant), puis à supprimer un autre élément/sommet aléatoire (pas descendant). Nous prouvons que ces chaînes convergent dans la limite des grandes tailles et après renormalisation du temps vers une diffusion de Feller sur l'espace des permutons et des graphons, respectivement. Nous obtenons également une formule explicite pour la distance de séparation entre la distribution des chaînes après n pas, excluant l'apparition d'un phénomène de “cut-off”. Notre approche fonctionne dans un cadre plus général : il est basé sur des relations de commutation entre les opérateurs des pas montants et descendants, et s'inspire des travaux de Fulman, Olshanski et Borodin–Olshanski sur l'espace des partitions et le simplex de Thoma. Je ne supposerai aucune connaissance préalable des permutons, graphons, diffusions de Feller, distances de séparation, seuils, ... Travail joint (et encore en cours) avec Kelvin Rivera-Lopez, Gonzaga University.[-]

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/[-]