Lemme local de Lovász

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 deux hypothèses : il y a au plus k littéraux par clause (c'est le problème k-SAT) et chaque littéral n’apparaît que dans au plus ${\displaystyle 2^{k/50}}$ clauses. Alors le lemme permet de dire que la formule est satisfiable[7]. En effet, si les valeurs des variables sont prises au hasard, alors les événements « la clause numéro i est satisfaite » satisfont les hypothèses du lemme symétrique avec ${\displaystyle p=2^{-k}}$ et ${\displaystyle d=k2^{k/50}}$.