Lemme local de Lovász

Le lemme local de Lovász (parfois abrégé LLL^{[réf. nécessaire]}) 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 ${\displaystyle (E_{i})_{i}}$, 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 ${\displaystyle E_{u}}$ et ${\displaystyle E_{v}}$ 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^[1].

S'il existe une famille de réels ${\displaystyle (x_{i})_{i}}$ de [0,1] tel que pour tout i :

${\displaystyle Pr[E_{i}]\leq x_{i}\Pi _{(i,j)\in E}(1-x_{j})}$

Alors :

${\displaystyle Pr[\cap _{i=1}^{n}{\bar {E_{i}}}]\geq \Pi _{i=1}^{n}(1-x_{i})}$

Si pour tout i, ${\displaystyle Pr[E_{i}]\leq p}$, 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 ${\displaystyle ep(d+1)\leq 1}$, où e est la base du logarithme naturel, alors ${\displaystyle Pr[\cap _{i=1}^{n}{\bar {E_{i}}}]>0}$.

Le lemme local a été utilisé dans de nombreux domaines de la combinatoire, notamment la théorie des graphes extrémaux, la théorie de Ramsey^[2] et la théorie des graphes aléatoires^[3], ainsi qu'en informatique théorique, notamment pour un cas particulier du problème SAT, pour des algorithmes de routage^[4],[5] et pour des problèmes de coloration^[6].

Le problème SAT, consiste, étant donné une formule logique sous forme normale conjonctive, de savoir s'il existe une assignation des variables telle que la formule est vraie, c'est-à-dire à décider la satisfiablilité de la formule. On fait trois hypothèses : il y a exactement k littéraux par clause (c'est une variante du problème k-SAT), chaque variable n’apparaît que dans au plus ${\displaystyle T={2^{k} \over ek}-{1 \over k}}$ clauses et au plus une fois par clause. Alors le lemme permet de dire que la formule est satisfiable. En effet, si les valeurs des variables sont prises au hasard uniformément et en posant ${\displaystyle E_{i}}$ l'événement « la clause numéro i est satisfaite Â», on a que chaque ${\displaystyle E_{i}}$ est dépendant d'au plus ${\displaystyle kT}$ autres événements et ${\displaystyle P(E_{i})\leq 2^{-k}}$. Ainsi les hypothèses du lemme symétrique sont satisfaites avec ${\displaystyle p=2^{-k}}$ et ${\displaystyle d=kT}$.

Considérons un collier avec 11n perles coloriées avec n couleurs telles que chaque couleur soit présente sur exactement 11 perles. Alors il existe un ensemble de n perles non adjacentes, toutes de couleurs différentes.

Pour montrer cela, on choisit aléatoirement une perle par couleur uniformément. Les mauvais événements correspondent au fait de choisir les paires ${\displaystyle (i,i+1\mod 11n)}$. Il y a 11n tels événements.

Pour chaque événement, la probabilité de sélectionner les deux bouts est au plus ${\displaystyle p={1 \over 11^{2}}}$ (avec égalité si les boules consécutives sont de couleur différente et 0 sinon). Le choix d'une paire (a,b) ne dépend que des événements dont les perles ont des couleurs en commun avec les perles a et b. Il y a 11 perles (dont a) de la même couleur que a donc 21 paires contenant la couleur de a (en excluant (a,b)). Le même raisonnement s'applique aux perles de la même couleur que b. On peut donc fixer ${\displaystyle d=42}$.

On a alors ${\displaystyle ep(d+1)\approx 0,966<1}$, ce qui nous permet d'appliquer le lemme symétrique.

Par le lemme local de Lovász, on a donc une probabilité strictement positive qu'aucune des paires de la forme ${\displaystyle (i,i+1)}$ ne soit de la même couleur et il existe donc un ensemble qui vérifie ces conditions.

Soit ${\displaystyle A_{1},A_{2},\dots ,A_{k}}$ une suite d'événements de probabilité au plus p tels que chacun dépendant d'au plus d autres.

Lemme I (Erdős et Lovász 1975) Si

${\displaystyle 4pd\leq 1}$

alors il y a une probabilité non nulle qu'aucun de ces événements ne se produise.

Lemma II (Lovász 1977; publié par Joel Spencer^[7]) Si

${\displaystyle ep(d+1)\leq 1,}$

où e = 2.718... est la base du logarithme népérien, alors il y a une probabilité non nulle qu'aucun de ces événements ne se produise.

Lemme III (Shearer 1985^[8]) Si

${\displaystyle {\begin{cases}p<{\frac {(d-1)^{d-1}}{d^{d}}}&d>1\\p<{\tfrac {1}{2}}&d=1\end{cases}}}$

alors il y a une probabilité non nulle qu'aucun de ces événements ne se produise.

La borne du Lemme III est optimale et implique que la borne

${\displaystyle epd\leq 1}$

est aussi suffisante.

Les premières preuves du lemme étaient non-constructives, mais une preuve constructive a été trouvée autour de 2010, par Robin A. Moser et Gábor Tardos^[9],[10]. Cela leur a valu en 2020 le Prix Gödel. Cette dernière preuve a aussi des conséquences algorithmiques, on parle d'ailleurs de lemme local de Lovász algorithmique (en). La méthode utilisée est appelée compression de l'entropie (en).

• (en) Paul ErdÅ‘s et László Lovász, « Problems and results on 3-chromatic hypergraphs and some related questions Â», dans Infinite and Finite Sets (to Paul ErdÅ‘s on his 60th birthday), vol. II, 1975 (lire en ligne), p. 609–627

• (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re Ã©d., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 5.5 (« The Lovász local lemma Â»), p. 115-120

• Samuel Regamey, Méthode probabiliste et Lemme local de Lovász (Rapport de projet), EPFL, janvier 2012 (lire en ligne)

• Portail des mathématiques
• Portail de l'informatique théorique
• Portail des probabilités et de la statistique