Lemme local de Lovász

Le lemme local de Lovász (parfois abrégé LLL) est un résultat de théorie des probabilités discrètes, dû à László Lovász et Paul Erdős. Il généralise le fait que la probabilité que des événements indépendants arrivent en même temps est égale au produit des probabilités de ces événements. Il existe plusieurs versions de ce résultat. Le lemme local est utilisé dans plusieurs domaines, notamment en combinatoire et en informatique théorique. Dans ces domaines il est parfois énoncé informellement de la manière suivante : étant donné un ensemble de mauvais événements, n'ayant pas de grande dépendances les uns avec les autres, il est possible d'éviter tous ces événements à la fois. Le lemme local peut être vu comme une version de la méthode probabiliste. Cette technique de combinatoire permet de montrer que certains objets existent en montrant que selon certaines constructions aléatoires la probabilité de créer un tel objet est non nul. Par exemple, étant donné une famille d'événements indépendants, de probabilités strictement inférieures à 1, la probabilité qu'aucun d'eux n'apparaissent est non nulle. Le lemme local peut permettre d'obtenir le même résultat, si chaque événement n'est dépendant que d'un nombre borné d'autres événements. Dans la suite, on note les événements , dans un espace de probabilité quelconque. Les dépendances entre ces événements peuvent être représentées par un graphe non orienté G=(V,E), appelé graphe des dépendances, défini par : chaque nœud représente un événement, une arête (u,v) appartient au graphe si et seulement si les événements et sont dépendants. On donne d'abord l'énoncé général, puis la forme symétrique qui en est un corollaire, plus facilement utilisable. S'il existe une famille de réels de [0,1] tel que pour tout i : Alors : Si pour tout i, , si chaque événement ne dépend que d'au plus d autres événements, i.e si le graphe de dépendances est de degré maximum d, et si , où e est la base du logarithme naturel, alors .