Cours spécifique à la filière Maths-Informatique : Introduction à la combinatoire
Au sujet de ce cours
Type de cours: Leçons (~2.5h /semaine) et Travaux dirigés (~1.5h /semaine)
Mode d’evaluation: Examen
Prérequis:
La plupart des étudiant·es n’ayant eu qu’un contact limité voire nul avec la combinatoire, il n’y a quasiment pas de prérequis, si ce n’est des bases mathématiques de tronc commun L2. Certaines parties toucheront à un peu d’analyse complexe mais on s’efforcera de le faire sans prérequis.
Résumé
Ce cours est une introduction à la combinatoire, à la fois dans le sens usuel en français de « combinatoire énumérative » mais aussi au sens plus large de « mathématiques discrètes », avec une insistance particulière autour des motivations et points de vue probabilistes. Nous ferons un compromis entre la largeur et la profondeur, en gardant un fil conducteur autour des objets aléatoires discrets mais en explorant diverses techniques classiques et modernes.
Plan approximatif, suivant comment on avance, avec de nombreux développements possibles en TD: Combinatoire énumérative et asymptotique basique (série génératrices, arbres, transferts, lemmes cycliques). Applications probabilistes classiques (fonctions aléatoires, second moment). Collecteur de coupons et variantes. Combinatoire signée (cribles), inclusion-exclusion. Combinatoire extrémale I: théorie de Ramsey, méthode probabiliste. Combinatoire extrémale II: Lemme de régularité de Szemerédi, triangle removal lemma.
Nous ne parlerons pas de combinatoire algébrique (représentations du groupe symétrique etc) ni de géométrie énumérative (énumération de courbes ou surfaces discrètes) mais ces développements ne sont pas très loin pour les personnes que ça intéresserait. Nous ne parlerons pas du lien entre combinatoire et logique.