Finding an easy example applying the general Lovász local lemma

Question

Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.

---

General Lovász local lemma: Consider a set $\mathcal{E}=\{A_1,\ldots,A_n\}$ of events such that each $A_i$ is mutually indepedent of $\mathcal{E}-(\mathcal{D}_i\cup A_i)$, for some $\mathcal{D}_i\subseteq \mathcal{E}$.

If we have reals $x_1,\ldots,x_n\in [0,1)$ such that for each $1\leq i\leq n$, $$Pr(A_i)\leq x_i \prod_{A_j\in \mathcal{D}_i}(1-x_j)$$ then the probability that none of the events in $\mathcal{E}$ occur is positive.

Answer 1

$\newcommand\D{\mathcal D}$A very simple application of this lemma is given as Corollary 6.1.6 in these lecture notes. In your notations, that corollary states the following:

If $Pr(A_i)<1/2$ and $\sum_{A_j\in\D_i}Pr(A_j)\le1/4$ for all $i$, then with positive probability none of the events $A_i$ occurs.

The proof of this corollary consists in letting $x_i:=2Pr(A_i)$ and using the inequalities $\prod_{A_j\in\D_i}(1-x_j)\ge1-\sum_{A_j\in\D_i}x_j\ge1/2$.

Answer 2

One of my favorite sources when I was learning about the local lemma was Notes on Randomized Algorithms by James Aspnes. There, the general local lemma from the OP is Lemma 11.3.1. In Sec 11.3.3, Aspnes gives several basic applications. In 11.3.3.1, he writes:

Let’s start with a simple application of the local lemma where we know what the right answer should be. Suppose we want to color the vertices of a cycle with c colors, so that no edge has two endpoints with the same color. How many colors do we need? Using brains, we can quickly figure out that c = 3 is enough. Without brains, we could try coloring the vertices randomly.

Here the bad events are when we end up with a monochromatic edge. Aspnes applies the local lemma to find the probability of ending up with a good coloring, for various values of $c$.

11.3.3.2 is Satisfiability of k-CNF formulas, a well-known application. The goal is to find an assignment of variables to truth values so that the set of clauses is mutually satisfiable.

11.3.4 is the well-known application of the local lemma to dependency graphs.

These lecture notes also contain great exercises that are applications of the local lemma, like A.6.2 about futile word search puzzles and C.3.2 about error-correcting codes.

An application to k-SAT is here, which also has an application to packet routing and to edge-coloring a complete graph (the classical Ramsey questions that kicked off the probabilistic method, but now approached using the local lemma).

In Sections 6.7-6.9 of the book Probability and Computing, you can also find applications of the local lemma to finding Edge Disjoint Paths in a graph, and k-SAT again. The exercises get into bounding the number of vertex disjoint paths, existence of list-colorings of a graph where you assign each vertex $v$ a color from some set $S(v)$ with $8r$ colors for some $r\geq 1$, and finding independent sets in a graph given some partition into disjoint subsets of size 4.

Here are some more applications of the local lemma that I gathered together while a student at BSM in Budapest, a long time ago:

1. Assume that $S$ is a finite set. If $|T| > {|S| \choose 2}$ then there exists an injective function $f:S\to T$.

2. Let $H$ be a hypergraph in which every edge has at least $k$ vertices and intersects at most $d$ other edges. Prove that, if $4d \leq 2^{k-1}$ then $H$ is 2-colorable without monochromatic edges. Then, prove the same if $e(d+1) \leq 2^{k-1}$.

3. Let $G$ be a cycle of length $4n$ and let $V = V_1 \cup \dots \cup V_n$ be a partition of its $4n$ vertices into $n$ pairwise disjoint subsets, each of cardinality 4. Prove that there existss an independent set of $G$ containing precisely one vertex from each $V_i$.

4. Prove that, for every integer $d > 1$, there is a finite $c(d)$ such that the edges of any bipartite graph with max degree $d$ in which every cycle has at least $c(d)$ edges can be colored by $d+1$ colors so that there are no two adjacent edges with the same color and there is no two-colored cycle.

5. Suppose $G$ is a directed graph with maximum in-degree $D$ and minimum out-degree $d$. Prove that for any $k > 0$, if $e(dD+1) (1-\frac{1}{k})^d \leq 1$ then there must exist a directed cycle in $D$ of length $0 (mod k)$.

6. Let $G$ be a graph such that the vertex set has a disjoint partition $V = V_1 \cup \dots \cup V_r$. Say that $T$ is a traversal if it contains exactly one element from each $V_i$, and an independent traversal if it is also an independent set. Let $D$ be the max degree in $G$. Prove that there exists an independent traversal if $|V_i| \geq 2 eD$ for every $i$.

7. A $k$-coloring of $\mathbb{R}$ is a function from the real numbers to a set of $k$ colors. Say a set $T$ of real numbers is rainbow if $T$ contains elements of every color. Let $m$ and $k$ be two positive integers satisfying $e(m(m-1)+1)k(1-\frac{1}{k})^m \leq 1$. Prove that, for any set $S$ of $m$ real numbers, there is a $k$-coloring such that every set $x+S$, for every real $x$, is multicolored.

8. Prove that there is a constant $c > 0$ such that, for every $k$ there is a set $S_k$ of at least $ck ln(k)$ integers, such that for every coloring of the integers by $k$ colors there is an integer $x$ for which the set $x+S$ does not intersect all color classes.