MAT741 - Géométrie combinatoire

Cible(s) de formation

Être capable de connaître les concepts clés reliés à une notion très générale d'indépendance ainsi que les techniques d'ordre et de dénombrement associées, de reconnaître lors d'exposés et de travaux ces concepts dans différentes situations concrètes venant de l'algèbre, de la géométrie, de la combinatoire, des graphes et de l'informatique, de les exploiter et d'en tirer les conséquences naturelles dans tous les cas simples et dans la majorité des cas relativement complexes.

Contenu

Treillis distributifs et modulaires, théorème de Birkhoff. Treillis géométriques et matroïdes. Fermetures, bases, circuits, dépendance. Matroïdes vectoriels et graphiques. Morphismes et morphismes forts. Algorithmes gloutons et matroïdes, greedoïdes. Fonctions de Möbius, algèbre d'incidence. Applications à la combinatoire, aux graphes et à l'algorithmique.