لم محلی لوواس یکی از لمهای ترکیبیات است که در نظریه احتمالات استفاده میشود. در نظریه احتمالات، چنانچه تعداد زیادی از پیشامدهای دو به دو مستقل داشته باشیم و احتمال وقوع هر کدام کمتر از یک باشد، احتمالی (هر چند کوچک) وجود دارد که هیچکدام از آنها اتفاق نیفتند. لم لوواس شرط استقلال پدیدهها را تا حدودی نادیده میگیرد؛ طبق این لم، تا وقتی که پیشامدها «اکثراً» از یکدیگر مستقلند و احتمال وقوع هر یک بهتنهایی خیلی زیاد نیست، احتمال رخ ندادن هیچیک از آنها وجود دارد. این لم بیشتر در متدهای ترکیبیاتی و بهطور خاص در مسئلههای اثبات وجود (به انگلیسی: existence proofs) کاربرد دارد. نسخههای زیادی از این لم وجود دارد. سادهترین و پرکاربردترین آن نسخه متقارن است که از نسخه نامتقارن بدست میآید.
نسخه نامتقارن لم لوواس
[ویرایش] چنانچه مجموعهای از پیشامدها در فضای نمونهای Ω باشد، برای هرکدام از اعضای A, همسایههای A در گراف وابستگی (اعضایی که نسبت به A مستقل نیستند) را نشان میدهد. اگر تابعی مانند وجود داشته باشد که:
آنگاه درباره احتمال رخ ندادن هیچیک از اعضای A رابطه زیر صادق است:
در نظر بگیرید.
مجموعه تعریف شدهاست. اگر بتوانیم نشان دهیم ، آنگاه قضیه بهراحتی اثبات میشود؛ زیرا خواهیم داشت:
جهت اثبات این رابطه، را تعریف میکنیم.
فرض میکنیم
از نتایج بدست آمده در نامساویهای (۱) و (۲) میتوان نامساوی زیر را بدست آورد:
چنانچه A1, A2,... , Ak مجموعهای از پیشامدهایی باشد که احتمال رخ دادن هرکدام حداکثر است و هریک حداکثر به پیشامد دیگر وابسته میباشد، سه قضیه زیر را داریم:
اگر ، آنگاه داریم:
اگر ، آنگاه:
اگر ، آنگاه:
نسخه متقارن با قرار دادن بهطور مستقیم از نسخه نامتقارن بدست میآید. در اینصورت بهدلیل اینکه ، میتوان نتیجه گرفت:
و در نتیجه داریم:
- از لم لواس میتوان برای نشان دادن این که یک ابرگراف مشخص، همیشه یک رنگآمیزی دوتایی دارد، استفاده کرد.[۱] یک ابرگراف، یک زوج به شکل نشان داد که نشان دهندهٔ رئوس و نشان دهندهٔ ابریالها است. هر ابریال، یک زیرمجموعه از رئوس است. یک رنگآمیزی دوتایی، تناظری است از رئوس به مجموعهٔ دو رنگ آبی و قرمز بهطوریکه هیچ ابریالی وجود نداشته باشد که تماماً یکرنگ باشد.
یک ابرگراف است که هر یال آن، شامل حداقل رٵس است و با حداکثر یال دیگر اشتراک دارد. برای چه و هایی، دارای رنگآمیزی دوتایی است؟ حل: ما یک رنگآمیزی تصادفی با احتمال یونیفرم را در نظر میگیریم. در نظر بگیرید حالتی باشد که یال تکرنگ شده باشد. احتمال وقوع این اتفاق، برابر است با: اگر این مقدار را برابر با در نظر بگیریم، باید را طوری در نظر بگیریم که شرایط لم لواس برقرار شود؛ یعنی . این نامساوی با قرار دادن بدست میآید.
در مسٵلهٔ m ,k-SAT عبارت داده شدهاست که هر کدام k جمله دارند. فرض کنید پیشامدی باشد که در آن، عبارت i-ام درست نباشد؛ یعنی تمام k جملهٔ آن غلط باشد. در این صورت، گراف وابستگی به این شکل تعریف میشود :
اگر و تنها اگر و حداقل یک جملهٔ مشترک داشته باشند.
میدانیم هر با یک احتمال محدود شدهاست و احتمال اتفاق افتادنش حداکثر است. خواستهٔ مسٵله، است. برای بدست آوردن شرایط لم لوواس، باید داشته باشیم: که در اینجا، همان بیشترین درجه است و داشتیم . در نتیجه داریم:
به این نتیجه میرسیم که هر رٵس در گراف وابستگی، باید حداکثر با رٵس دیگر همسایه باشد.