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 « secondaires ». 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.

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr