The Art of Computer Programming: Satisfiability, Volume 4, Fascicle 6

355. [HM21] In (152), prove that E_j ≤ 1/δ when (p₁, . . . , p_m) has positive slack δ. Hint: Consider replacing p_j by p_j + δp_j.

356. [M33] (The Clique Local Lemma.) Let G be a graph on {1, . . . , m}, and let G | U₁, . . . , G | U_t be cliques that cover all the edges of G. Assign numbers θ_ij ≥ 0 to the vertices of each U_j, such that Σ_j = ∑_{i ∈ U j} θ_ij < 1. Assume that

a) Prove that (p₁, . . . , p_m) ∈ R(G). Hint: Letting denote , show that

b) Also ...