Séminaire de la détente mathématique

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

par Aline Parreau

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

Salle de conférences (1er étage)

Maison des mathématiques et de l'informatique

1 place de l'École - 69007 Lyon
Description
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.
Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×