Proof of Property B Bound via Lovász Local Lemma

A hypergraph has Property B (is 2-colorable) if its vertices can be colored with two colors such that no edge is monochromatic. We prove a sharp sufficient condition using the Lovász Local Lemma.

Statement

Theorem7.5Property B via LLL

Let $\mathcal{H} = (V, \mathcal{E})$ be a $k$ -uniform hypergraph where every edge intersects at most $d$ other edges. If $d \leq 2^{k-1}/e - 1$ , then $\mathcal{H}$ has Property B.

Proof

Color each vertex independently and uniformly at random with red or blue. For each edge $e \in \mathcal{E}$ , let $A_e$ be the bad event that $e$ is monochromatic. Then: $\Pr[A_e] = 2 \cdot \left(\frac{1}{2}\right)^k = 2^{1-k}.$

Dependency graph: Two events $A_e$ and $A_f$ are dependent only if $e \cap f \neq \emptyset$ . Since each edge intersects at most $d$ other edges, the dependency graph has maximum degree $d$ .

Applying the symmetric LLL: We need $e \cdot \Pr[A_e] \cdot (d + 1) \leq 1$ , i.e., $e \cdot 2^{1-k} \cdot (d + 1) \leq 1.$

This is equivalent to $d + 1 \leq 2^{k-1}/e$ , which holds by assumption.

By the Lovász Local Lemma: $\Pr\left[\bigcap_{e \in \mathcal{E}} \overline{A_e}\right] > 0.$

Therefore a proper 2-coloring exists, and $\mathcal{H}$ has Property B. $\square$

■

Discussion and Improvements

ExampleTightness of the Bound

The bound $d \leq 2^{k-1}/e$ is essentially tight. There exist $k$ -uniform hypergraphs with $d = \Theta(2^k)$ that are not 2-colorable. For instance, Erdos showed using the probabilistic method that random $k$ -uniform hypergraphs on $n$ vertices with $\Theta(n \cdot 2^k)$ edges are not 2-colorable with high probability.

RemarkConstructive Version

The Moser-Tardos algorithm makes this proof constructive: given the hypergraph satisfying the condition, one can efficiently find a proper 2-coloring. The algorithm randomly colors vertices, then iteratively resamples the colors of vertices in monochromatic edges. The expected number of resampling steps is at most $|\mathcal{E}| / (1 - e \cdot 2^{1-k}(d+1)) = O(|\mathcal{E}|)$ .

ExampleIndependent Transversals

A related application: Let $G$ be a graph with vertex partition $V_1 \cup \cdots \cup V_n$ where $|V_i| \geq 2ed + 1$ and each vertex has at most $d$ neighbors in each other part. Then $G$ has an independent transversal (a set choosing one vertex from each part with no edges between chosen vertices). This follows from the LLL with events $A_{e}$ for each edge $e$ between parts.

RemarkEntropy Compression

The entropy compression method (Esperet-Parreau 2013) can sometimes beat the LLL bound. By analyzing the information content of the algorithm's execution, one obtains bounds of the form $d \leq 2^{k-1}(1 - o(1))$ , removing the factor of $e$ in the denominator for large $k$ .