Lema local de Lovász

En teoria de provabilitat, si una cantitat gran d'events és tal que qualsevol parella d'ells és tal que un és independent de l'atre, i ademés cada event té provabilitat menor que 1, llavors hi ha una provabilitat positiva -possiblement menuda-. que cap dels acontenyiments ocórrega. El Lema local de Lovász relaixa la condició d'independència llaugerament: Sempre i quan els acontenyiments siguen "majoritàriament" independents un de l'atre, i no siguen massa provables individualment, llavors encara es pot concloure que hi ha una provabilitat positiva que cap d'ells ocórrega. Este lema és utilisat majoritàriament en el método provabiliste, en particular per a donar proves d'existència.

Hi ha vàries versions diferents del lema. La més senzilla i més freqüentment utilisada és el la versió simètrica. Una versió més dèbil va ser provada en 1975 per László Lovász i Paul Erdős en l'artícul Problemes i resultats sobre hipergrafos 3-cromàtics i preguntes relacionades. Atres versions es troben en ( Alon & Spencer 2000 ). En 2020, Robin Moser i Gábor Tardos varen rebre el Premi Gödel gràcies a la seua versió algorítmica del Lema Local de Lovász.

Variants del lema (Versió simètrica)

Siga

$A_1,A_2,\dots ,A_k$

una seqüència d'events tal que cada u d'ells ocorre en probabilidad com a molt

$p$

i tal que cada event és independent de tots els atres, llevat com a màxim

$d$

d'ells.

Lema I (Lovász i Erdős 1973; publicat en 1975) Si

$4pd\le 1$

llavors la provabilitat que cap dels events ocórrega és major que zero.

Lema II (Lovász 1977; publicat per Joel Spencer) Si

$ep(d+1)\le 1,$

a on i = 2.718... és la base dels logaritmos naturals, llavors la provabilitat que cap dels events ocórrega és major que zero.

Lema II és normalment referit hui com el 'Lema Local de Lovász'.

Lema III (Shearer 1985) Si

$\{\begin{array}{cc}p<\frac{(d-1{)}^{d-1}}{d^d}& d>1\\ p<\frac{1}{2}& d=1\end{array}$

llavors la provabilitat que cap dels events ocórrega és major que zero.

El llindar en Lema III és optimal, i açò implica que la quota

$epd\le 1$

És ademés suficient.

Asimètric Lovász lema local

Una formulació més general que aquella de la versió asimètrica (la qual permet que els events tinguen distintes quotes de provabilitat) és la següent:

Lema (versió asimètrica). Siga

$𝒜=\{A_1,\dots ,A_n\}$

un conjunt finito d'events en un espai de provabilitat Ω. Per a

$A\in 𝒜$

, denotem

$\Gamma (A)$

els veïns de

$A$

en el grafo de dependència (en dit grafo de dependència, un event

$A$

és solament adjacent a aquells que depenen d'est, o dels quals depén). Si existix una assignació d'número real als acontenyiments

$x:𝒜\to [0,1)$

tal que

$\mathrm{\forall }A\in 𝒜:\mathrm{Pr}(A)\le x(A)\prod _{B\in \Gamma (A)}(1-x(B))$

Llavors la provabilitat d'evitar tots els acontenyiments en $𝒜$ és positiu; en particular

$\mathrm{Pr}(\overline{A_1}\wedge \cdots \wedge \overline{A_n})\ge \prod _{i\in \{1,\cdot \cdot \cdot ,n\}}(1-x(A_i)).$

La versió simètrica seguix immediatament de la versió asimètrica en assignar els valors:

$\mathrm{\forall }A\in 𝒜:x(A)=\frac{1}{d+1}$

de lo que conseguim la condició suficient

$p\le \frac{1}{d+1}\cdot \frac{1}{e}$

ya que

$\frac{1}{e}\le {(1-\frac{1}{d+1})}^d.$

Notes

1. ↑

1. ↑
2. ↑

Referències

• Alon, Noga; Spencer, {{{nom2}}} (2000). The probabilistic method, 2nd edició, New York: Wiley-Interscience. ISBN 0-471-37046-0.
• (1991).Random Structures and Algorithms.2(4)

343–365.doi:10.1002/rsa.3240020402.

• (2000).Random Structures & Algorithms.17(3–4)

213–237.doi:10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-I.

• Erdos, Paul; Lovász, László (1975) 'Problems and results on 3-chromatic hypergraphs and some related questions' (PDF) En
•  Moser, Robin A. (2008). 'Una prova constructiva del Lema Local de Lovasz'. arXiv:0810.4812 [cs.DS]