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).