Soutenance de thèse de Khaydar Nurligareev
[English version of this page]
Titre
Irréductibilité des objets combinatoires : probabilité asymptotique et interprétation
Résumé
De nombreuses structures combinatoires admettent, au sens large, une notion d’irréductibilité : les graphes peuvent être connexes, les permutations indécomposables, les polynômes irréductibles, etc. Dans cette thèse, nous nous intéressons à la probabilité qu'un tel objet pris au hasard soit irréductible, lorsque sa taille tend vers l'infini. On obtient des développements asymptotiques complets pour ces probabilités ; l'irréductibilité est comprise à travers les constructions combinatoires SET, SEQ et CYC dans le contexte de la méthode symbolique. Nous appliquons notre approche aux graphes connexes, aux tournois irréductibles, aux permutations indécomposables et aux couplages parfaits. En outre, nous établissons des asymptotiques pour plusieurs modèles de surfaces connexes comprenant les surfaces à petits carreaux, les cartes combinatoires et certains objets de dimension supérieure tels que les constellations et les modèles de tenseurs colorés. Nous montrons que les coefficients apparaissant dans ces asymptotiques sont entiers et qu'ils peuvent être interprétés comme des suites de comptage d'autres classes combinatoires « dérivées ». Par exemple, les graphes connexes conduisent aux tournois irréductibles, les surfaces à petits carreaux aux permutations indécomposables, les cartes combinatoires aux couplages parfaits indécomposables. De plus, nous obtenons certaines probabilités asymptotiques qu'un objet combinatoire aléatoire ait un nombre donné de composantes irréductibles. Passant de la méthode symbolique à la théorie des espèces, nous traitons également le modèle G(n,p) de Erdös–Rényi. Nous établissons également la probabilité qu'un graphe orienté aléatoire soit fortement connexe en utilisant une décomposition plus complexe qui implique des graphes acycliques orientés.
Jury
- Jason Bell — Université de Waterloo — Rapporteur
- Olivier Bodini — Université Sorbonne Paris Nord — Éxaminateur
- Marthe Bonamy — CNRS & Université de Bordeaux — Éxaminatrice
- Sylvie Corteel — CNRS & Université Paris Diderot — Rapportrice
- Thierry Monteil — CNRS & Université Sorbonne Paris Nord — Co-directeur de thèse
- Igor Pak — Université de Californie à Los Angeles — Rapporteur
- Lionel Pournin — Université Sorbonne Paris Nord — Directeur de thèse