لم لوواس

چنانچه ${\displaystyle \mathcal{A}=\{A_1,\dots ,A_n\}}$

آنگاه درباره احتمال رخ ندادن هیچ‌یک از اعضای A رابطه زیر صادق است:

اثبات نسخه نامتقارن

در نظر بگیرید${\displaystyle S=\{B_1,B_2,...,B_m\}}$

مجموعه ${\displaystyle {\overline{P}}_S=Pr\left(\overline{B_1}\wedge \cdots \wedge \overline{B_n}\right)}$

${\displaystyle \overline{P_{\mathcal{A}}}\ge (1-x_{A_1})\overline{P_{\mathcal{A}/A_1}}\ge ...\ge (1-x_{A_1})...(1-x_{A_n})\overline{P_{\mathrm{\varnothing }}}=(1-x_{A_1})...(1-x_{A_n})\ge 0}$

جهت اثبات این رابطه، ${\displaystyle {\mathrm{\Gamma }}^{+}(b)=b\vee \mathrm{\Gamma }(b)}$

فرض می‌کنیم ${\displaystyle \mathcal{\Gamma }\mathcal{(}{\mathcal{B}}_{\mathcal{1}}\mathcal{)}\wedge \mathcal{S}=\{B_2,\dots ,B_k\}}$

${\displaystyle =>{\overline{P}}_S=P[{\overline{B}}_1\wedge ...\wedge {\overline{B}}_m]=P[{\overline{B}}_2\wedge ...\wedge {\overline{B}}_m]-P[B_1\wedge {\overline{B}}_2\wedge ...\wedge {\overline{B}}_m]\ge P[{\overline{B}}_2\wedge ...\wedge {\overline{B}}_m]-P[B_1\wedge {\overline{B}}_{k+1}\wedge ...\wedge {\overline{B}}_m]={\overline{P}}_{S/B_1}-{\overline{P}}_{S/{\mathrm{\Gamma }}^{+}(B_1)}P[B_1]}$

${\displaystyle =>\frac{{\overline{P}}_S}{{\overline{P}}_{S/B_1}}\ge 1-\frac{{\overline{P}}_{S/{\mathrm{\Gamma }}^{+}(B_1)}}{{\overline{P}}_{S/B_1}}\cdot P[B_1]\ge 1-x_{B_1}(1)}$

${\displaystyle \frac{{\overline{P}}_{S/{\mathrm{\Gamma }}^{+}(B_1)}}{{\overline{P}}_{S/B_1}}=\frac{{\overline{P}}_{S/B_1,B_2}}{{\overline{P}}_{S/B_1}}\cdot \frac{{\overline{P}}_{S/B_1,B_2,B_3}}{{\overline{P}}_{S/B_1,B_2}}...\frac{{\overline{P}}_{S/B_1,B_2,...,B_k}}{{\overline{P}}_{S/B_1,...,B_{k-1}}}(2)}$

از نتایج بدست آمده در نامساوی‌های (۱) و (۲) می‌توان نامساوی زیر را بدست آورد:

${\displaystyle =>\frac{{\overline{P}}_{S/{\mathrm{\Gamma }}^{+}(B_1)}}{{\overline{P}}_{S/B_1}}\le \frac{1}{1-x_{B_2}}\cdot \frac{1}{1-x_{B_3}}\cdot \cdot \cdot \frac{1}{1-x_{B_k}}}$

${\displaystyle =>\frac{{\overline{P}}_S}{{\overline{P}}_{S/B_1}}\ge 1-\prod _2^k\frac{1}{1-x_{B_i}}\cdot Pr[B_i]\ge 1-\prod _2^k\frac{1}{1-x_{B_i}}\cdot \prod _{c\in \mathrm{\Gamma }(B_1)}(1-x_c)\cdot x_{B_1}\ge 1-x_{B_1}}$

چنانچه A₁, A₂,... , A_k مجموعه‌ای از پیشامدهایی باشد که احتمال رخ دادن هرکدام حداکثر ${\displaystyle p}$

• لم I

اگر ${\displaystyle 4pd\le 1}$

• لم II

اگر ${\displaystyle e\cdot p\cdot (d+1)\le 1,}$

• لم III

اگر

اثبات نسخه متقارن

نسخه متقارن با قرار دادن ${\displaystyle \mathrm{\forall }A\in \mathcal{A}:x(A)=\frac{1}{d+1}}$

و در نتیجه داریم:

• از لم لواس می‌توان برای نشان دادن این که یک ابرگراف مشخص، همیشه یک رنگ‌آمیزی دوتایی دارد، استفاده کرد. یک ابرگراف، یک زوج به شکل ${\displaystyle H=(V,E)}$
  نشان داد که ${\displaystyle V}$
  نشان دهندهٔ رئوس و ${\displaystyle E}$
  نشان دهندهٔ ابریال‌ها است. هر ابریال، یک زیرمجموعه از رئوس است. یک رنگ‌آمیزی دوتایی، تناظری است از رئوس به مجموعهٔ دو رنگ آبی و قرمز به‌طوری‌که هیچ ابریالی وجود نداشته باشد که تماماً یک‌رنگ باشد.

${\displaystyle H=(V,E)}$

• در این مثال، ما یک گراف وابستگی را رویمسئله صدق‌پذیری دودویی(به انگلیسی: K-SAT) تعریف می‌کنیم و با استفاده از لم لوواس، جواب داشتن مسٵله را بررسی می‌کنیم.

در مسٵلهٔ m ,k-SAT عبارت داده شده‌است ${\displaystyle (C_i)}$

${\displaystyle \{A_i,A_j\}\in E}$

می‌دانیم هر ${\displaystyle A_i}$

${\displaystyle \frac{e(d+1)}{2^k}\le 1\Rightarrow }$

${\displaystyle (d+1)\le \frac{2^k}{e}\Rightarrow }$

${\displaystyle d\le \frac{2^k}{e}-1}$

به این نتیجه می‌رسیم که هر رٵس در گراف وابستگی، باید حداکثر با ${\displaystyle \frac{2^k}{e}-1}$

• احتمالات
• پیشامدهای مستقل