La combinatoire est l'étude des structures discrètes qui apparaissent en informatique, en mathématiques, en physique statistique, en biologie, et en fait un peu partout.

Les familles les plus étudiées sont certaines familles d'arbres, de chemins, de permutations, de tableaux, de cartes combinatoires, de polynômes... Une liste un peu plus longue est donnée à la fin de cette page.

L'activité principale de ce groupe est l'obtention de théorèmes, résultats de nature mathématique donc, décrivant les structures discrètes en question, leurs relations, et leur comportement. Ces résultats s'appliquent notamment à l'analyse d'algorithmes et à l'étude de modèles de physique statistique.

Combinatoire énumérative

Il s'agit ici de trouver des décompositions des objets, de trouver le nombre d'objets ayant une taille donnée, et de trouver des bijections entre différentes familles d'objets.

Combinatoire algébrique

Les liens entre combinatoire et algèbre existent dans les deux directions. En effet, la résolution de questions de nature algébrique passe parfois par l'énumération d'objets combinatoires. Par ailleurs, munir des objets combinatoires d'une structure algébrique (à votre avis, que signifie T * T' quand T et T' sont des arbres?) peut aider à leur compréhension.

Combinatoire probabiliste

À quoi ressemble un objet typique de taille donnée ? Plusieurs attaques sont possibles ici : trouver des méthodes de génération aléatoire, calculer la limite en loi de certains paramètres, et même prouver la convergence globale des objets, vers des objets continus aléatoires, après normalisation.

Analyse d'algorithmes

Souvent les algorithmes construisent ou parcourent des structures combinatoires, et leur analyse repose sur l'étude de ces structures. C'est pour cela que cette spécialité est représentée dans notre groupe. Il s'agit ici, en général, d'une analyse en moyenne ou en distribution.

Une liste non exhaustive des objets plus particulièrement étudiés

Algèbres de Hopf, animaux dirigés (ou non), arbres (dont arbres binaires de recherche, arbres simplement générés, arbres de Galton-Watson, arbres étiquetés, décorés, profil vertical, théorèmes limites), cartes (dont triangulations, quadrangulations, cartes colorées, hypercartes, intégrales de matrices, théorèmes limites), chemins (de Dyck, confinés dans le quart de plan, auto-évitants, qui ne se croisent pas), empilements, Ewens sampling formula, fonctions symétriques, fonctions de Belyi, extensions linéaires, fonctions de parking, génération aléatoire (Boltzmann, couplage venu du passé), matrices à signes alternants (Fully packed loops, avec symétrie), modèles de génération de Boltzmann, pavages, permutations (dont tableaux de permutations, tableaux de Young, partitions, permutations évitant des motifs, classes de permutations, permutations de Baxter, représentations du groupe symétrique), polynômes (symétriques, de Kerov, de Jack, de Tutte), modèle du tas de sable, "tree-like" tableaux, Watermelons.

Les méthodes

Les outils de la combinatoire sont très divers : analyse fonctionnelle, algèbre, géométrie algébrique, théorie des probabilités, génération aléatoire, génération exhaustive, calcul formel, analyse complexe.

Retour vers la page de l'équipe


Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar