لم لوواس

**لم محلی لوواس** یکی از لم‌های ترکیبیات است که در نظریه احتمالات استفاده می‌شود. در نظریه احتمالات، چنانچه تعداد زیادی از پیشامدهای دو به دو مستقل داشته باشیم و احتمال وقوع هر کدام کمتر از یک باشد، احتمالی (هر چند کوچک) وجود دارد که هیچ‌کدام از آن‌ها اتفاق نیفتند. لم لوواس شرط استقلال پدیده‌ها را تا حدودی نادیده می‌گیرد؛ طبق این لم، تا وقتی که پیشامدها «اکثراً» از یکدیگر مستقلند و احتمال وقوع هر یک به‌تنهایی خیلی زیاد نیست، احتمال رخ ندادن هیچ‌یک از آن‌ها وجود دارد. این لم بیشتر در متدهای ترکیبیاتی و به‌طور خاص در مسئله‌های اثبات وجود  کاربرد دارد. نسخه‌های زیادی از این لم وجود دارد. ساده‌ترین و پرکاربردترین آن نسخه متقارن است که از نسخه نامتقارن بدست می‌آید.

## نسخه نامتقارن لم لوواس
چنانچه  \mathcal{A} = \{ A_1, \ldots, A_n \} مجموعه‌ای از پیشامدها در فضای نمونه‌ای Ω باشد، برای هرکدام از اعضای A,  \Gamma(A) همسایه‌های A در گراف وابستگی (اعضایی که نسبت به A مستقل نیستند) را نشان می‌دهد. اگر تابعی مانند x : \mathcal{A} \to [0,1)  وجود داشته باشد که:

 \forall A \in \mathcal{A} : \Pr(A) \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) 

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

 \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) \geq \prod_{i\in [n]} (1-x(A_i))

### اثبات نسخه نامتقارن
در نظر بگیرید S= \{B_1,B_2,...,B_m\}.

مجموعه \overline P_S =\Pr\left(\overline{B_1} \wedge \cdots \wedge \overline{B_n} \right)  تعریف شده‌است. اگر بتوانیم نشان دهیم \frac {\overline P_S}{\overline P_{S /b}}\geq 1-x_b، آنگاه قضیه به‌راحتی اثبات می‌شود؛ زیرا خواهیم داشت:

\overline {P_{\mathcal A }}\geq (1-x_{A_1}) \overline {P_{\mathcal A /{A_1}}}\geq ... \geq (1-x_{A_1})...(1-x_{A_n}) \overline {P_\emptyset} = (1-x_{A_1})...(1-x_{A_n}) \geq 0

جهت اثبات این رابطه، \Gamma^+(b)=b\vee \Gamma(b) را تعریف می‌کنیم.

فرض می‌کنیم \mathcal {\Gamma(B_1) \wedge S}=\{ B_2, \ldots, B_k \}

=> \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] \geq 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/\Gamma^+(B_1)} P[B_1]

=> \frac {\overline P_S}{\overline P_{S/B_1}} \geq 1- \frac{\overline P_{S/\Gamma^+(B_1)}}{\overline P_{S/B_1}}\cdot P[B_1] \geq 1- x_{B_1}(1)

 \frac{\overline P_{S/\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)

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

=> \frac {\overline P_{S/\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}}

 => \frac {\overline P_S}{\overline P_{S/B_1}} \geq 1- \prod_2^k \frac {1}{1-x_{B_i}} \cdot Pr[B_i] \geq 1-\prod_2^k \frac {1}{1-x_{B_i}}\cdot \prod_{c\in\Gamma(B_1)} (1-x_c) \cdot x_{B_1} \geq 1-x_{B_1} 

## نسخه متقارن لم لوواس
چنانچه *A*1, *A*2,... , *A**k* مجموعه‌ای از پیشامدهایی باشد که احتمال رخ دادن هرکدام حداکثر p است و هریک حداکثر به d پیشامد دیگر وابسته می‌باشد، سه قضیه زیر را داریم:
* **لم I**

اگر 4 p d \le 1، آنگاه داریم:

 \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 
* **لم II**

اگر e\cdot p\cdot (d+1) \le 1,، آنگاه:

 \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 
* **لم III**

اگر \begin{cases} p  1\\ p ، آنگاه:

 \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 

### اثبات نسخه متقارن
نسخه متقارن با قرار دادن  \forall A \in \mathcal{A} : x(A) = \frac{1}{d+1} به‌طور مستقیم از نسخه نامتقارن بدست می‌آید. در این‌صورت به‌دلیل اینکه \frac{1}{e} \leq \left (1 - \frac{1}{d+1} \right)^d، می‌توان نتیجه گرفت:

 p \leq \frac{1}{d+1} \cdot \frac{1}{e} 

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

e\cdot p\cdot (d+1) \le 1

## مثال‌ها
* از لم لواس می‌توان برای نشان دادن این که یک ابرگراف مشخص، همیشه یک رنگ‌آمیزی دوتایی دارد، استفاده کرد. یک ابرگراف، یک زوج به شکل H=(V,E) نشان داد که V نشان دهندهٔ رئوس و E نشان دهندهٔ ابریال‌ها است. هر ابریال، یک زیرمجموعه از رئوس است. یک رنگ‌آمیزی دوتایی، تناظری است از رئوس به مجموعهٔ دو رنگ آبی و قرمز به‌طوری‌که هیچ ابریالی وجود نداشته باشد که تماماً یک‌رنگ باشد.
H=(V,E) یک ابرگراف است که هر یال آن، شامل حداقل k رٵس است و با حداکثر d یال دیگر اشتراک دارد. برای چه k و d‌هایی، H دارای رنگ‌آمیزی دوتایی است؟
**حل:** ما یک رنگ‌آمیزی تصادفی با احتمال یونیفرم را در نظر می‌گیریم. در نظر بگیرید  \lbrace A_e \rbrace حالتی باشد که یال e تک‌رنگ شده باشد. احتمال وقوع این اتفاق، برابر است با:
P[\lbrace A_e \rbrace] = (\frac {1} {2})^{k} + (\frac {1} {2})^{k} = 2^{1-k}
اگر این مقدار را برابر با p در نظر بگیریم، باید d را طوری در نظر بگیریم که شرایط لم لواس برقرار شود؛ یعنی ep(d+1) \le 1. این نامساوی با قرار دادن d \le \frac {2^{1-k}} {e} -1 بدست می‌آید.
* در این مثال، ما یک گراف وابستگی را رویمسئله صدق‌پذیری دودویی تعریف می‌کنیم و با استفاده از لم لوواس، جواب داشتن مسٵله را بررسی می‌کنیم.
در مسٵلهٔ m ,k-SAT عبارت داده شده‌است (C_i) که هر کدام k جمله دارند. فرض کنید  A_i پیشامدی باشد که در آن، عبارت i-ام درست نباشد؛ یعنی تمام k جملهٔ آن غلط باشد.
در این صورت، گراف وابستگی به این شکل تعریف می‌شود :
V={A_1,A_2,\cdots,A_m}

\{A_i, A_j\} \in E اگر و تنها اگر C_i و C_j حداقل یک جملهٔ مشترک داشته باشند.

می‌دانیم هر A_i با یک احتمال p = Pr[A_i] = Pr[\neg C_i] = \frac {1} {2^{k}} محدود شده‌است و احتمال اتفاق افتادنش حداکثر p است. خواستهٔ مسٵله،  \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_m} \right) >0  است. برای بدست آوردن شرایط لم لوواس، باید داشته باشیم:
ep(d+1) \leq 1 که در این‌جا، d همان بیشترین درجه است و داشتیم p = \frac {1} {2^{k}} . در نتیجه داریم:

 \frac {e(d+1)} {2^k} \leq 1 \Rightarrow

(d+1) \leq \frac {2^k} {e} \Rightarrow

d \leq \frac {2^k} {e} -1

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

## جستارهای وابسته
* احتمالات
* پیشامدهای مستقل

## منابع

* https://en.wikipedia.org/wiki/Lovász_local_lemma
* Jan Vondr�ak,"Non-constructive methods in combinatorics",Stanford University",Spring 2016
* 
 

رده:ترکیبیات
رده:قضیه‌های احتمالات
رده:لم‌ها
رده:نظریه احتمالات
رده:وابستگی آماری