نمایش مبدأ برای لم لوواس

'''لم محلی لوواس''' یکی از [[لم (ریاضیات)|لم‌های]] [[ترکیبیات]] است که در نظریه [[احتمالات]] استفاده می‌شود. در نظریه احتمالات، چنانچه تعداد زیادی از پیشامدهای دو به دو مستقل داشته باشیم و احتمال وقوع هر کدام کمتر از یک باشد، احتمالی (هر چند کوچک) وجود دارد که هیچ‌کدام از آن‌ها اتفاق نیفتند. لم لوواس شرط استقلال پدیده‌ها را تا حدودی نادیده می‌گیرد؛ طبق این لم، تا وقتی که پیشامدها «اکثراً» از یکدیگر مستقلند و احتمال وقوع هر یک به‌تنهایی خیلی زیاد نیست، احتمال رخ ندادن هیچ‌یک از آن‌ها وجود دارد. این لم بیشتر در متدهای ترکیبیاتی و به‌طور خاص در مسئله‌های اثبات وجود {{به انگلیسی|existence proofs}} کاربرد دارد. نسخه‌های زیادی از این لم وجود دارد. ساده‌ترین و پرکاربردترین آن نسخه متقارن است که از نسخه نامتقارن بدست می‌آید.

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

{{وسط‌چین}}<math> \forall A \in \mathcal{A} : \Pr(A) \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) </math>{{پایان}}

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

{{وسط‌چین}}<math> \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) \geq \prod_{i\in [n]} (1-x(A_i))</math>{{پایان}}

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

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

<math>\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</math>

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

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

<math>=> \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]</math>

<math>=> \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)</math>

<math> \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)</math>

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

<math>=> \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}}</math>

<math> => \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} </math>

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

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

{{وسط‌چین}}<math> \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 </math>{{پایان}}
* '''لم II'''

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

{{وسط‌چین}}<math> \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 </math>{{پایان}}
* '''لم III'''

اگر <math>\begin{cases} p < \frac{(d-1)^{d-1}}{d^d} & d > 1\\ p < \tfrac{1}{2} & d = 1 \end{cases}</math>، آنگاه:

{{وسط‌چین}}<math> \Pr\left(\overline{A_1} \wedge \cdots \wedge \overline{A_n} \right) >0 </math>{{پایان}}

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

{{وسط‌چین}}<math> p \leq \frac{1}{d+1} \cdot \frac{1}{e} </math>{{پایان}}

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

{{وسط‌چین}}<math>e\cdot p\cdot (d+1) \le 1</math>{{پایان}}

== مثال‌ها ==
* از لم لواس می‌توان برای نشان دادن این که یک [[ابرگراف]] مشخص، همیشه یک رنگ‌آمیزی دوتایی دارد، استفاده کرد.<ref>http://theory.epfl.ch/courses/topicstcs/Lecture2.pdf</ref> یک ابرگراف، یک زوج به شکل <math>H=(V,E)</math> نشان داد که <math>V</math> نشان دهندهٔ رئوس و <math>E</math> نشان دهندهٔ ابریال‌ها است. هر ابریال، یک زیرمجموعه از رئوس است. یک رنگ‌آمیزی دوتایی، تناظری است از رئوس به مجموعهٔ دو رنگ آبی و قرمز به‌طوری‌که هیچ ابریالی وجود نداشته باشد که تماماً یک‌رنگ باشد.
<math>H=(V,E)</math> یک ابرگراف است که هر یال آن، شامل حداقل <math>k</math> رٵس است و با حداکثر <math>d</math> یال دیگر اشتراک دارد. برای چه <math>k</math> و <math>d</math>‌هایی، <math>H</math> دارای رنگ‌آمیزی دوتایی است؟
'''حل:''' ما یک رنگ‌آمیزی تصادفی با احتمال یونیفرم را در نظر می‌گیریم. در نظر بگیرید <math> \lbrace A_e \rbrace</math> حالتی باشد که یال <math>e</math> تک‌رنگ شده باشد. احتمال وقوع این اتفاق، برابر است با:
<math>P[\lbrace A_e \rbrace] = (\frac {1} {2})^{k} + (\frac {1} {2})^{k} = 2^{1-k}</math>
اگر این مقدار را برابر با <math>p</math> در نظر بگیریم، باید <math>d</math> را طوری در نظر بگیریم که شرایط لم لواس برقرار شود؛ یعنی <math>ep(d+1) \le 1</math>. این نامساوی با قرار دادن <math>d \le \frac {2^{1-k}} {e} -1</math> بدست می‌آید.
* در این مثال، ما یک گراف وابستگی را روی[[مسئله صدق‌پذیری دودویی]]{{به انگلیسی|K-SAT}} تعریف می‌کنیم و با استفاده از لم لوواس، جواب داشتن مسٵله را بررسی می‌کنیم.<ref>http://www.cse.iitm.ac.in/~jayalal/teaching/CS6845/2012/lecture-A06.pdf{{پیوند مرده|date=مه ۲۰۲۰ |bot=InternetArchiveBot}}</ref>
در مسٵلهٔ m ,k-SAT عبارت داده شده‌است <math>(C_i)</math> که هر کدام k جمله دارند. فرض کنید <math> A_i</math> پیشامدی باشد که در آن، عبارت i-ام درست نباشد؛ یعنی تمام k جملهٔ آن غلط باشد.
در این صورت، گراف وابستگی به این شکل تعریف می‌شود :
<math>V={A_1,A_2,\cdots,A_m}</math>

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

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

<math> \frac {e(d+1)} {2^k} \leq 1 \Rightarrow</math>

<math>(d+1) \leq \frac {2^k} {e} \Rightarrow</math>

<math>d \leq \frac {2^k} {e} -1</math>

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

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

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* https://en.wikipedia.org/wiki/Lovász_local_lemma
* Jan Vondr�ak,"Non-constructive methods in combinatorics",Stanford University",Spring 2016
* {{cite book
 | last1 = Alon | first1 = Noga | author1-link = Noga Alon
 | last2 = Spencer | first2 = Joel H. | author2-link = Joel H. Spencer
 | edition = 2nd
 | isbn = 0-471-37046-0
 | location = New York
 | publisher = Wiley-Interscience
 | ref = harv
 | title = The probabilistic method
 | year = 2000}}
 {{پایان چپ‌چین}}

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