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