Den Lovász lokale lemma (undertiden forkortet LLL ) er et resultat af sandsynlighedsregning diskret på grund af László Lovász og Paul Erdős . Det generaliserer det faktum, at sandsynligheden for, at uafhængige begivenheder finder sted på samme tid, er lig med produktet af sandsynligheden for disse begivenheder. Der er flere versioner af dette resultat. Det lokale lemma bruges inden for flere områder, især i kombinatorik og i teoretisk datalogi . På disse områder er det undertiden uformelt angivet som følger: givet et sæt dårlige begivenheder, der ikke har stor afhængighed af hinanden, er det muligt at undgå alle disse begivenheder på samme tid.
Det lokale lemma kan ses som en version af den sandsynlige metode . Denne kombinatoriske teknik gør det muligt at vise, at bestemte objekter eksisterer ved at vise, at sandsynligheden for at skabe et sådant objekt ifølge visse tilfældige konstruktioner ikke er nul.
For eksempel, givet en familie af uafhængige begivenheder med sandsynligheder strengt mindre end 1, er sandsynligheden for, at ingen af dem vises, ikke-nul. Det lokale lemma kan gøre det muligt at opnå det samme resultat, hvis hver begivenhed kun er afhængig af et begrænset antal andre begivenheder.
I det følgende betegner vi begivenhederne i et vilkårligt sandsynlighedsrum.
Afhængighederne mellem disse begivenheder kan repræsenteres af en ikke-rettet graf G = (V, E) , kaldet afhængighedsgrafen , defineret af:
Vi giver først den generelle erklæring, derefter den symmetriske form, der er en følge, lettere anvendelig.
Hvis der findes en familie af reelle tal på [0,1] sådan at for alle i :
Så:
Hvis for hver i , hvis hver begivenhed kun afhænger på de fleste af andre begivenheder, dvs hvis afhængighed grafen er af grad op til , og hvis , hvor e er den base af den naturlige logaritme , så .
Det lokale lemma er blevet brugt i mange områder af kombinatorik, herunder ekstrem grafteori , Ramsey-teorien og teorien om tilfældige grafer , og i teoretisk datalogi, især i et specielt tilfælde af SAT-problemet , til routingsalgoritmer og til farvelægningsproblemer .
Det SAT Problemet består, får en logisk formel i konjunktiv normalform , for at vide, om der er en opgave for de variabler, således at formlen er sand, det vil sige at bestemme opfyldelighed af formlen. Vi antager to antagelser: der er højst k literaler pr. Sætning (dette er k -SAT- problemet ), og hver bogstavelig vises kun i højst klausuler. Derefter tillader lemmaet at sige, at formlen er tilfredsstillende. Faktisk, hvis værdierne af variablerne tages tilfældigt, tilfredsstiller begivenhederne "klausul nummer i er opfyldt" antagelserne fra det symmetriske lemma med og .
Det lokale lemma blev offentliggjort i artiklen Erdős og Lovász 1975 med en stærkere hypotese . Det blev forbedret for at få de rammer, der er givet her. De første beviser for lemmaet var ikke-konstruktive, men konstruktive bevis blev fundet omkring 2010 af Moser og Tardos. Dette sidste bevis har også algoritmiske konsekvenser, man taler desuden om algoritmisk Lovász lokale lemma ( fr ) . Den anvendte metode kaldes entropikompression (en) .