Evènement pour le groupe GT Graphes et Applications

Date 2013-04-19  14:00-15:00
TitreApplications of an algorithmic proof of Lovasz Local Lemma 
RésuméThe Lovasz Local Lemma is a powerful tool to give existential proofs of combinatorial objects with some properties. It says that if some events happen with small probabilities and are not too much dependent of each other, the probability that no event happens is positive. Recently, Moser gave an algorithmic proof of this lemma, based on entropy compression. I will explain the ideas of this very elegant method that leads to constructive and strong results trough two examples : acyclic edge coloring of graphs and non-repetitive words. This is based on joint work with Louis Esperet (G-SCOP, Grenoble, France). 
LieuSalle 178 
OrateurAline Parreau 
UrlUniv. Lille 

Aucun document lié à cet événement.

Retour à l'index