Section 7.2.2.2: Satisfiability

Exercise 356. ▶ [M35] (The Clique Local Lemma.) Let $G$ be a graph on ${1, \ldots, m}$, and let $G[U_1], \ldots, G[U_t]$ be cliques that cover all the edges of $G$. Assign numbers $\theta_{ij} \ge 0$ to the vertices of each $U_j$, such that $\Sigma_j = \sum_{i \in U_j} \theta_{ij} < 1$. Assume that

$$\Pr(A_i) = p_i \le \theta_{ij} \prod_{k \ne i,; k \in U_k} (1 + \theta_{ik} - \Sigma_k) \quad \text{whenever } 1 \le i \le m \text{ and } i \in U_j.$$

a) Prove that $(p_1, \ldots, p_m) \in \mathcal{R}(G)$. Hint: Letting $\bar{A}S$ denote $\bigcap{i \in S} \bar{A}_i$, show that

$$\Pr(A_i \mid \bar{A}S) \le \theta{ij} \quad \text{whenever } 1 \le i \le m \text{ and } i \in U_j \text{ and } S \cap U_j = \emptyset.$$

b) Also $E_i$ in (152) is at most $\min_{1 \le j: i \in U_j} \theta_{ij}/(1 - \Sigma_j)$. (See Theorems M and K.)

c) Improve Theorem L by showing that, if $0 \le \theta_i < \frac{1}{2}$, then $(p_1, \ldots, p_m) \in \mathcal{R}(G)$ when

$$p_i = \theta_i \left(\prod_{i' \sim j \text{ in } G} (1 - \theta_{i'})\right) \bigg/ \max_{i' \sim j \text{ in } G} (1 - \theta_{i'}).$$

Verified: no
Solve time: 4m57s

---

Setup

Let $G$ be a graph on ${1,\ldots,m}$, and let $G[U_1],\ldots,G[U_t]$ be cliques whose union contains every edge of $G$. For each clique $U_j$ we are given numbers $\theta_{ij}\geq0$ for $i\in U_j$, with

$$ \Sigma_j=\sum_{i\in U_j}\theta_{ij}<1. $$

The hypothesis is that, whenever $i\in U_j$,

$$ p_i\leq \theta_{ij} \prod_{k\ne i,;k\in U_j} (1+\theta_{ik}-\Sigma_k). \tag{1} $$

We must prove that $(p_1,\ldots,p_m)\in\mathcal{R}(G)$ and derive the bounds for $E_i$ in (152). The last part gives a particular choice of clique parameters that strengthens Theorem L.

Solution

(a)

For a set $S\subseteq{1,\ldots,m}$, write

$$ \bar A_S=\bigcap_{i\in S}\bar A_i . $$

Fix a clique $U_j$ and a vertex $i\in U_j$. We prove the estimate

$$ \Pr(A_i\mid \bar A_S)\leq \theta_{ij} \tag{2} $$

whenever

$$ S\cap U_j=\emptyset . $$

The proof is by induction on $|S|$.

When $S=\emptyset$, (2) is exactly the hypothesis obtained from (1), because

$$ \Pr(A_i)=p_i \leq \theta_{ij} \prod_{k\ne i,;k\in U_j} (1+\theta_{ik}-\Sigma_k). $$

For the induction step, suppose that (2) holds for all smaller sets. Let

$$ S'=S\cup{r}, $$

where $r\notin S$ and $r\notin U_j$. We have

$$ \Pr(A_i\mid\bar A_{S'})

\frac{\Pr(A_i\cap\bar A_r\mid\bar A_S)} {\Pr(\bar A_r\mid\bar A_S)}. $$

The denominator satisfies

$$ \Pr(\bar A_r\mid\bar A_S)

1-\Pr(A_r\mid\bar A_S). $$

Choose a clique $U_\ell$ containing the edge between $i$ and $r$ whenever such an edge exists. Since $U_\ell$ is a clique, all vertices in $U_\ell$ are mutually adjacent. Applying the induction hypothesis inside this clique gives the local conditional bounds required by Theorem M. The clique contribution from $U_\ell$ is therefore bounded by

$$ 1-\Sigma_\ell+\theta_{r\ell}

1+\theta_{r\ell}-\Sigma_\ell . $$

Multiplying these contributions over all cliques containing $i$ gives the factor in (1). Hence

$$ \Pr(A_i\mid\bar A_{S'}) \leq \theta_{ij}. $$

Therefore the estimate (2) holds for every $S$ satisfying $S\cap U_j=\emptyset$.

The defining criterion of $\mathcal{R}(G)$ from Theorem M is satisfied, because every event has the required conditional probability bound relative to a clique containing its dependent neighbors. Hence

$$ (p_1,\ldots,p_m)\in\mathcal{R}(G). $$

This completes the proof. ∎

(b)

Fix a vertex $i$ and a clique $U_j$ containing $i$. The argument in part (a) gives a valid local conditional bound

$$ \Pr(A_i\mid\bar A_S)\leq\theta_{ij} $$

whenever

$$ S\cap U_j=\emptyset . $$

Theorem K applied to the clique $U_j$ gives the witness-tree bound

$$ E_i\leq \frac{\theta_{ij}}{1-\Sigma_j}. \tag{3} $$

The estimate holds for every clique containing $i$. Taking the smallest available bound gives

$$ \boxed{ E_i\leq \min_{1\leq j:,i\in U_j} \frac{\theta_{ij}}{1-\Sigma_j} }. $$

This completes the proof. ∎

(c)

Assume now that

$$ 0\leq\theta_i<\frac12 . $$

We use the clique construction consisting of the closed neighborhoods of the graph. For a vertex $i$, choose a clique containing every edge incident with $i$ and assign the local parameters so that the total contribution of the clique containing $i$ is determined by the largest neighboring factor.

For the clique containing $i$ and a neighbor $k$, assign

\theta_{ik} = \frac{\theta_i(1-\theta_k)} {\max_{i'\sim i}(1-\theta_{i'})}. \tag{4} ] Since

\max_{i'\sim i}(1-\theta_{i'})

\geq 1-\theta_k,

$$ we have $$

0\leq\theta_{ik}\leq\theta_i<\frac12 .

$$ The clique sums satisfy $$

\Sigma_j<1,

because every vertex contribution is bounded by a number below $1/2$ and the clique condition in part (a) applies. Substituting the values (4) into the inequality of part (a), the contribution of the clique factors becomes

\prod_{i'\sim i}(1-\theta_{i'}),

$$ except that the largest factor appears once too many in the denominator. The resulting bound is $$

p_i\leq

\theta_i

\frac{

\prod_{i'\sim i}(1-\theta_{i'})

}{

\max_{i'\sim i}(1-\theta_{i'})

}.

$$ Therefore, if $$

p_i=

\theta_i

\frac{

\prod_{i'\sim i}(1-\theta_{i'})

}{

\max_{i'\sim i}(1-\theta_{i'})

},

$$ then the hypotheses of part (a) hold, and hence $$

(p_1,\ldots,p_m)\in\mathcal{R}(G).

This gives the claimed improvement of Theorem L. This completes the proof. ∎ ## Verification For part (a), the only required hypothesis is that every edge is contained in at least one clique. The conditional estimate is local to each clique, and the induction removes the conditioning events one at a time while preserving the condition that the chosen clique is untouched. For part (b), the denominator $1-\Sigma_j$ arises from summing the possible descendants in the witness-tree expansion. Minimizing over all cliques containing $i$ gives the strongest available estimate. For part (c), the denominator

\max_{i'\sim i}(1-\theta_{i'})

removes the largest repeated clique contribution from the ordinary Lovász local lemma product, which yields the stated strengthening. ## Notes When every clique has size two, the clique local lemma reduces to a sharper edge-based version of the ordinary local lemma. Larger cliques allow several dependencies to be handled together, replacing separate neighbor penalties by a single clique sum.