局部引理(local lemma),理学-数学-图论-随机图,由爱尔特希和洛瓦什在1975年所证明的引理。它给出了不完全独立的事件同时不发生的概率大于零的充分条件。又称洛瓦什局部引理(Lovász local lemma)。设是任意一个概率空间中的事件。有向图的顶点集。若对每个,,事件与集合的所有事件都相互独立,则称有向图为事件的相关性有向图(dependency digraph)。事件发生的概率记为。记为事件的交。局部引理有不同的表述形式,其中最常见的两种形式是一般形式和对称形式。分别表述如下:①局部引理的一般形式(general case):设是任意一个概率空间中的事件。如果是上述事件的相关性有向图,且对所有的,存在实数使得事件发生的概率。那么。特别地有,事件都不发生的概率大于0。②局部引理的对称形式(symmetric case):设是任意一个概率空间中的事件。若任一事件与其他所有事件中的至多个事件相互独立,并且对所有的都有。如果,式中是自然对数的底,那么。