Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 9 Avril 2013

Applications d'une preuve algorithmique du Lemme Local de Lovász

par Aline Parreau (LIFL, Lille)

Le lemme local de Lovasz est un outil très utilisé permettant de montrer de manière simple l'existence d'objets combinatoires avec certaines propriétés. Il dit que si des événements ont lieu avec une petite probabilité et ne sont pas trop indépendants les uns des autres, la probabilité qu'aucun événement n'arrive est non nulle. Moser a donné en 2009 une preuve algorithmique de ce lemme, basée sur la compression d'entropie. Cette méthode permet en outre, dans certains cas, d'obtenir de manière élégante des résultats plus fort que ceux obtenus en utilisant le lemme local. J'expliquerai ses idées principales à travers deux exemples : la construction de mots sans carré et la coloration acyclique des arêtes d'un graphe.

Travaux réalisés avec Louis Esperet (G-SCOP, Grenoble).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr