لم لوواس

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

نسخه نامتقارن لم لوواس

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

${\displaystyle \forall A\in {\mathcal {A}}:\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

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

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod _{i\in [n]}(1-x(A_{i}))}$

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

در نظر بگیرید${\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 {\frac {{\overline {P}}_{S}}{{\overline {P}}_{S/b}}}\geq 1-x_{b}}$، آنگاه قضیه به‌راحتی اثبات می‌شود؛ زیرا خواهیم داشت:

${\displaystyle {\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}$

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

فرض می‌کنیم ${\displaystyle {\mathcal {\Gamma (B_{1})\wedge S}}=\{B_{2},\ldots ,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}]\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}]}$

${\displaystyle =>{\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)}$

${\displaystyle {\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)}$

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

${\displaystyle =>{\frac {{\overline {P}}_{S/\Gamma ^{+}(B_{1})}}{{\overline {P}}_{S/B_{1}}}}\leq {\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}}}}\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₁, A₂,... , A_k مجموعه‌ای از پیشامدهایی باشد که احتمال رخ دادن هرکدام حداکثر ${\displaystyle p}$ است و هریک حداکثر به ${\displaystyle d}$ پیشامد دیگر وابسته می‌باشد، سه قضیه زیر را داریم:

• لم I

اگر ${\displaystyle 4pd\leq 1}$، آنگاه داریم:

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)>0}$

• لم II

اگر ${\displaystyle e\cdot p\cdot (d+1)\leq 1,}$، آنگاه:

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)>0}$

• لم III

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

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)>0}$

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

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

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

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

${\displaystyle e\cdot p\cdot (d+1)\leq 1}$

مثال‌ها

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

${\displaystyle H=(V,E)}$ یک ابرگراف است که هر یال آن، شامل حداقل ${\displaystyle k}$ رٵس است و با حداکثر ${\displaystyle d}$ یال دیگر اشتراک دارد. برای چه ${\displaystyle k}$ و ${\displaystyle d}$‌هایی، ${\displaystyle H}$ دارای رنگ‌آمیزی دوتایی است؟ حل: ما یک رنگ‌آمیزی تصادفی با احتمال یونیفرم را در نظر می‌گیریم. در نظر بگیرید ${\displaystyle \lbrace A_{e}\rbrace }$ حالتی باشد که یال ${\displaystyle e}$ تک‌رنگ شده باشد. احتمال وقوع این اتفاق، برابر است با: ${\displaystyle P[\lbrace A_{e}\rbrace ]=({\frac {1}{2}})^{k}+({\frac {1}{2}})^{k}=2^{1-k}}$ اگر این مقدار را برابر با ${\displaystyle p}$ در نظر بگیریم، باید ${\displaystyle d}$ را طوری در نظر بگیریم که شرایط لم لواس برقرار شود؛ یعنی ${\displaystyle ep(d+1)\leq 1}$. این نامساوی با قرار دادن ${\displaystyle d\leq {\frac {2^{1-k}}{e}}-1}$ بدست می‌آید.

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

در مسٵلهٔ m ,k-SAT عبارت داده شده‌است ${\displaystyle (C_{i})}$ که هر کدام k جمله دارند. فرض کنید ${\displaystyle A_{i}}$ پیشامدی باشد که در آن، عبارت i-ام درست نباشد؛ یعنی تمام k جملهٔ آن غلط باشد. در این صورت، گراف وابستگی به این شکل تعریف می‌شود : ${\displaystyle V={A_{1},A_{2},\cdots ,A_{m}}}$

${\displaystyle \{A_{i},A_{j}\}\in E}$ اگر و تنها اگر ${\displaystyle C_{i}}$ و ${\displaystyle C_{j}}$ حداقل یک جملهٔ مشترک داشته باشند.

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

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

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

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

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

جستارهای وابسته

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

منابع

1. http://theory.epfl.ch/courses/topicstcs/Lecture2.pdf
2. http://www.cse.iitm.ac.in/~jayalal/teaching/CS6845/2012/lecture-A06.pdf%5Bپیوند+مرده%5D

• https://en.wikipedia.org/wiki/Lovász_local_lemma
• Jan Vondr�ak,"Non-constructive methods in combinatorics",Stanford University",Spring 2016
• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2nd ed.). New York: Wiley-Interscience. ISBN 0-471-37046-0.