La compression d'entropie en combinatoire (ou comment mettre le bazar peut --parfois-- aider les mathématiciens)

par Aline Parreau

mercredi 27 sept. 2017, 18:00 → 19:00 Europe/Paris

Salle de conférences (1er étage) (Maison des mathématiques et de l'informatique)

Pour prouver l'existence d'un objet mathématique avec contraintes, une technique assez classique consiste à générer aléatoirement l'objet et à prouver qu'il y a une probabilité non nulle pour que toutes les contraintes soient vérifiées. Des célèbres résultats comme le Lemme Local de Lovàsz (LLL) donnent des conditions sur l'indépendance et la probabilité des contraintes pour que cela fonctionne. En combinatoire, cette méthode a permis à de nombreux théorèmes de voir le jour. Son inconvénient majeur est qu'elle ne nous donne aucune construction pour le dit-objet. Récemment, Möser a trouvé une méthode constructive pour prouver le lemme local de Lovàsz, basée sur le principe de la compression d'entropie. Le but de cet exposé est de donner les idées de la méthode de Möser et ses implications en combinatoire. Rendez-vous à 17 h 30 pour un café, un thé, un gâteau, discussion avec l'oratrice... Exposé à 18 h.