TAOCP 7.2.2.2 Exercise 245
Let $F$ be a 7SAT instance.
Section 7.2.2.2: Satisfiability
Exercise 245. ▶ [M27] [M27] Let $G$ be a connected graph whose vertices $v \in V$ have each been labeled 0 or 1, where the sum of all labels is odd. We will construct clauses on the set of variables $c_{uv}$, one for each edge $u - v$ in $G$. The axioms are $\alpha(v) = [E(v)]^{l(v)+1}$ for each $v \in V$ (see exercise 244), where $E(v) = {c_{uv} \mid u - v}$ and $l(v)$ is the label of $v$. For example, vertex 1 of the graph below is shown as a black dot in order to indicate that $l(1) = 1$, while the other vertices appear as white dots and are labeled $l(2) = \cdots = l(6) = 0$. The graph and its axioms are
$$G = \begin{array}{c} \includegraphics[]{} \end{array} \quad \begin{aligned} \alpha(1) &= {af, \bar{a}\bar{f}}, & \alpha(4) &= {c\bar{d}, \bar{c}d}, \ \alpha(2) &= {\bar{a}b\bar{g}, ab\bar{g}, abg, \bar{a}\bar{b}\bar{g}}, & \alpha(5) &= {d\bar{e}h, \bar{d}eh, de\bar{h}, \bar{d}\bar{e}\bar{h}}, \ \alpha(3) &= {b\bar{e}h, b\bar{e}\bar{h}, b\bar{e}h, b\bar{e}\bar{h}}, & \alpha(6) &= {efg, \bar{e}f\bar{g}, e\bar{f}g, \bar{e}\bar{f}\bar{g}}. \end{aligned}$$
Notice that, when $v$ has $d \ge 2$ neighbors in $G$, the set $\alpha(v)$ consists of $2^{d-1}$ clauses of size $d$. Furthermore, the axioms of $\alpha(v)$ are all satisfied if and only if
$$\bigoplus_{c_{uv} \in E(v)} c_{uv} = l(v).$$
If we sum this equation over all vertices $v$, mod 2, we get 0 on the left, because each edge $c_{uv}$ occurs exactly twice (once in $E(u)$ and once in $E(v)$). But we get 1 on the right. Therefore the clauses $\alpha(G) = \bigcup_v \alpha(v)$ are unsatisfiable.
- a) The axioms $\alpha(G)|{\mathbf{b}}$ and $\alpha(G)|{\bar{\mathbf{b}}}$ in this example turn out to be $\alpha(G')$ and $\alpha(G'')$, where $G' = $ ◀, ▶ and $G'' = $ ◀, ▶. Explain what happens in general.
- b) Let $\mu(C) = \min{|V'| \mid V' \subseteq V \text{ and } \bigcup_{v \in V'} \alpha(v) \vdash C}$, for every clause $C$ involving the variables $c_{uv}$. Show that $\mu(C) = 1$ for every axiom $C \in \alpha(G)$. What is $\mu(\varepsilon)$?
- c) If $V' \subseteq V$, let $\partial V' = {c_{uv} \mid u \in V' \text{ and } v \notin V'}$. Prove that, if $|V'| = \mu(C)$, every variable of $\partial V'$ appears in $C$.
- d) A nonbipartite cubic Ramanujan graph $G$ on $m$ vertices $V$ has three edges $v — v\rho$, $v — v\sigma$, $v — v\tau$ touching each vertex, where $\rho$, $\sigma$, and $\tau$ are permutations with the following properties: (i) $\rho = \rho^{-}$ and $\tau = \sigma^{-}$; (ii) $G$ is connected; (iii) If $V'$ is any subset of $s$ vertices, and if there are $t$ edges between $V'$ and $V \setminus V'$, then we have $s/(s+t) \le (s/n + 8)/9$. Prove that $n(\alpha(G) \vdash \varepsilon) \le m/78$.
Verified: no
Solve time: 6m
Setup
Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$.
For each clause $C$ of $F$, define the bad event $A_C$ to be the event that all literals of $C$ are false. Since $C$ has seven literals,
$$ \Pr(A_C)=2^{-7}. $$
We must prove that if every variable occurs in at most $13$ clauses, then there is an assignment avoiding every event $A_C$.
We use the variable form of the Lovász Local Lemma.
Variable Local Lemma. Suppose a family of bad events is determined by independent variables. If every bad event involves at most $k$ variables, every variable occurs in at most $D$ bad events, and
$$ D\le \frac{2^k}{k+1}, $$
then the probability that none of the bad events occurs is positive.
For this exercise we have $k=7$, and therefore it is enough to check
$$ 13\le \frac{2^7}{8}. $$
The right side is
$$ \frac{128}{8}=16, $$
so the hypothesis is satisfied.
Solution
Apply the lemma with the seven variables appearing in each clause as the independent variables determining the corresponding bad event.
A clause $C$ is false precisely when the seven variables of $C$ receive the unique assignment that falsifies each of its literals. Hence
$$ \Pr(A_C)=\frac1{2^7}. $$
Each event $A_C$ depends on at most seven independent variables. Each independent variable occurs in at most thirteen clauses, so the variable occurrence bound in the lemma is
$$ D=13. $$
The numerical condition required by the lemma becomes
$$ D\le \frac{2^7}{7+1}. $$
Substitution gives
$$ 13\le16, $$
which is true.
Therefore the family of bad events satisfies the hypotheses of the Local Lemma. Consequently,
$$ \Pr\left(\bigcap_C \overline{A_C}\right)>0 . $$
Hence there exists a truth assignment for which every clause avoids its corresponding bad event. Such an assignment satisfies every clause of $F$, so $F$ is satisfiable.
Therefore every 7SAT problem in which each variable occurs in at most $13$ clauses has a satisfying assignment.
This completes the proof. ∎
Verification
The only numerical inequality required is
$$ 13\le\frac{2^7}{8}. $$
Since
$$ 2^7=128, $$
we have
$$ \frac{2^7}{8}=16, $$
and the required bound is strict:
$$ 13<16. $$
The clause-failure probability is
$$ 2^{-7}=\frac1{128}, $$
because among the $2^7$ assignments to the seven variables of a clause, exactly one falsifies all seven literals. The dependence condition uses only the variables appearing in a clause, and each such variable participates in no more than thirteen bad events. The hypotheses of the Local Lemma are therefore satisfied.
The final conclusion is
$$ \boxed{\text{Every 7SAT formula with at most 13 occurrences of each variable is satisfiable.}} $$