Den Lovász lokale lemma (noen ganger forkortet LLL ) er et resultat av sannsynlighetsteori diskret grunn László Lovász og Paul Erdős . Det generaliserer det faktum at sannsynligheten for at uavhengige hendelser oppstår samtidig er lik produktet av sannsynligheten for disse hendelsene. Det er flere versjoner av dette resultatet. Det lokale lemmaet brukes på flere felt, spesielt i kombinatorikk og i teoretisk informatikk . I disse områdene blir det noen ganger sagt uformelt som følger: gitt et sett med dårlige hendelser, uten stor avhengighet av hverandre, er det mulig å unngå alle disse hendelsene samtidig.
Det lokale lemmaet kan sees på som en versjon av den sannsynlige metoden . Denne kombinatoriske teknikken gjør det mulig å vise at visse objekter eksisterer ved å vise at sannsynligheten for å skape et slikt objekt i henhold til visse tilfeldige konstruksjoner ikke er null.
For eksempel, gitt en familie av uavhengige hendelser, med sannsynligheter strengt mindre enn 1, er sannsynligheten for at ingen av dem vises ikke null. Det lokale lemmaet kan gjøre det mulig å oppnå det samme resultatet, hvis hver hendelse bare er avhengig av et begrenset antall andre hendelser.
I det følgende betegner vi hendelsene , i et vilkårlig sannsynlighetsrom.
Avhengighetene mellom disse hendelsene kan representeres av en ikke-rettet graf G = (V, E) , kalt avhengighetsgrafen , definert av:
Vi gir først den generelle uttalelsen, deretter den symmetriske formen som er en følge, lettere brukbar.
Hvis det eksisterer en familie med reelle tall på [0,1] slik at for alle jeg :
Så:
Hvis for hver jeg , hvis hver hendelse avhenger bare på de fleste av andre hendelser, dvs. hvis avhengigheten grafen er av grad opp til , og hvis , hvor e er basen for den naturlige logaritmen , da .
Det lokale lemmaet har blitt brukt i mange områder av kombinatorikk, inkludert ekstrem grafteori , Ramsey-teorien og teorien om tilfeldige grafer , og i teoretisk informatikk, spesielt for et spesielt tilfelle av SAT-problemet , for rutealgoritmer og for fargeleggingsproblemer .
Det SAT problem består i, gitt en logisk formel i konjunktiv normalform , for å vite om det er en tilordning av de variable slik at formelen er oppfylt, det vil si for å bestemme den Satisfiability av formelen. Vi antar to forutsetninger: det er maksimalt k literaler per ledd (dette er k -SAT- problemet ) og hver bokstavelig vises bare i de fleste ledd. Da tillater lemmaet å si at formelen er tilfredsstillende. Hvis verdiene til variablene blir tatt tilfeldig, tilfredsstiller hendelsene "klausul nummer jeg er tilfredsstilt" hypotesene til det symmetriske lemmaet med og .
Det lokale lemmaet ble publisert i artikkelen Erdős og Lovász 1975 med sterkere hypotese . Det ble forbedret for å få grensene gitt her. De første bevisene for lemmaet var ikke-konstruktive, men konstruktive bevis ble funnet rundt 2010 av Moser og Tardos. Dette siste beviset har også algoritmiske konsekvenser, man snakker dessuten om algoritmisk Lovász lokale lemma ( fr ) . Metoden som brukes kalles entropikomprimering (en) .