论文部分内容阅读
洛瓦兹局部引理是组合数学和概率论中的重要工具,其最主要的用途之一是证明当约束之间"弱相关"时,满足复杂约束的组合对象存在.自从1975年Erdos和Lovasz提出洛瓦兹局部引理以来,局部引理在组合数学、理论计算机和物理学等领域已经有了很多应用.近年来,为了扩展局部引理的应用范围,人们提出了很多新版的局部引理,尤其是在构造版本局部引理上取得了重大的突破.本文将综述局部引理近年来最新的研究进展,包括几种最主要的局部引理变种以及它们在计算机科学和物理学中的应用.特别的,我们将给出抽象版本、Lopside