洛瓦茲局部引理（Lovasz Local Lemma）
/ LOH-vahs /
洛瓦茲局部引理是在聯集界失效時拯救機率方法的工具。基本方法藉由證明 P(某壞事件發生) < 1 來表明好物件存在，通常透過聯集界 P(B_i 之聯集) <= sum P(B_i)。但當壞事件很多時，即使每個個別事件都罕見，此和仍超過 1。若壞事件完全獨立，則只要每個 P(B_i) < 1，便有 P(無一發生) = product of (1 - P(B_i)) > 0，存在性平凡可得。現實介於兩極之間：壞事件通常既不互斥也不獨立，但每個事件只依賴少數其他事件。局部引理正是利用這種稀疏相依性。
建立一個相依圖：頂點是壞事件 B_1, ..., B_n，若 B_i 與所有不與它相鄰的事件之集合互相獨立，則 B_i 與 B_j 連邊（按相依關係）。對稱局部引理陳述：若每個 P(B_i) <= p，每個事件至多依賴 d 個其他事件，且判準 e * p * (d + 1) <= 1 成立（e = 2.718...，自然對數底），則 P(無壞事件發生) > 0——故存在避開所有壞事件的組態。一般（非對稱）形式以一個系統取代單一界：若能指派 (0,1) 中的數 x_i，使 P(B_i) <= x_i 乘以對其鄰居 j 的 (1 - x_j) 之積，則同樣 P(無一發生) > 0，事實上 P(無一發生) >= product of (1 - x_i) > 0。證明是一個歸納法，表明在避開其他任一子集的條件下每個 B_i 的條件機率仍低於 x_i。
其重要性在於它把「罕見且弱相依」轉成「可同時避開」，這是聯集界做不到的。經典應用：超圖的正常著色（每個顏色約束只觸及少數其他約束）、每個子句只與少數其他子句共用變數的 k-SAT 公式之可滿足性，以及許多相依度 d 增長但保持受控的結果。誠實的提醒是判準 ep(d+1) <= 1 不可或缺且本質上是緊的：它不是魔法。若壞事件太可能或相依太稠密，引理便毫無所獲，且常數 e 一般不能改進（Shearer 定出了確切門檻）。此外，經典引理是非建構式的——它證明存在卻在歷史上未給出有效率地找到好組態的方法，這個間隙後來才由 Moser-Tardos 填補。
k-SAT：一個合取範式公式，其中每個子句恰有 k 個文字且每個變數出現在少數子句中，則可滿足。用公平硬幣決定每個變數的真值。壞事件 B_i =「子句 i 未被滿足」的 P(B_i) = 2^(-k)。若每個子句至多與 d 個其他子句共用變數且 e * 2^(-k) * (d+1) <= 1，即 d <= 2^k/e - 1，則局部引理保證存在一組滿足賦值。相較之下，聯集界一旦子句超過 2^k 個便失效。
對稱局部引理：ep(d+1) <= 1 使罕見且稀疏相依的壞事件可同時避開。
局部引理不是魔法：判準 ep(d+1) <= 1（或非對稱 x_i 系統）不可或缺，常數 e 一般不能改進（Shearer 的界是緊的），且經典引理是非建構式的。