Lagmental Vicfred

The Lovász Local Lemma Handles Sparse Dependence by Vicfred

Last updated: Wed 21 June 2017

tags: mathematics, extremal combinatorics, probabilistic method, Ramsey theory

Bad events can all be avoided when each event is unlikely and depends on few others. The point is to make the formal expression readable enough to audit line by line.

Definitions first

Extremal combinatorics asks how large a structure can be while avoiding a forbidden configuration. The probabilistic method proves existence by showing \(\mathbf P(X=0)>0\) or \(\mathbf E[X]<1\).

$$ \mathbf P(A_i)\le p,\qquad A_i\ \text{depends on at most }d\text{ other events} $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ ep(d+1)\le1\Longrightarrow\mathbf P\!\left(\bigcap_i\overline{A_i}\right)>0 $$

A small case in full

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \left.\begin{aligned}\mathbf P(A_i)&\le p,\\x(1-x)^d&\ge p\end{aligned}\right\}\Longrightarrow\mathbf P\!\left(\bigcap_i\overline{A_i}\right)\ge(1-x)^m>0 $$

The reusable statement

The abstraction earns its keep by explaining why the same computation reappears. The notation compresses repeated reasoning without erasing the hypothesis that licenses it.

$$ \begin{aligned} \mathsf{D}\;&:\quad \mathbf P(A_i)\le p,\qquad A_i\ \text{depends on at most }d\text{ other events},\\[5pt] \mathsf{C}\;&:\quad ep(d+1)\le1\Longrightarrow\mathbf P\!\left(\bigcap_i\overline{A_i}\right)>0. \end{aligned} $$

A nearby false statement

An expectation below one proves that some outcome has zero bad objects only when the bad-object count is a nonnegative integer.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] ep(d+1)\le1\Longrightarrow\mathbf P\!\left(\bigcap_i\overline{A_i}\right)>0 \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Tue 25 February 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.