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: 6m06s

Solution

Write

$$ \alpha(V')=\bigcup_{v\in V'}\alpha(v) $$

for $V'\subseteq V$. Each $\alpha(v)$ is the CNF encoding of the parity equation

$$ \bigoplus_{c_{uv}\in E(v)}c_{uv}=l(v). $$

The contradiction in the full formula comes from adding all these equations over $GF(2)$. Every edge variable occurs twice and cancels, whereas the labels contribute

$$ \bigoplus_{v\in V}l(v)=1. $$

Hence $\alpha(G)$ is unsatisfiable.

(a)

Let an edge $u-v$ have variable $c_{uv}$, and suppose that we restrict this variable by

$$ c_{uv}=b,\qquad b\in{0,1}. $$

The parity equation at $u$ becomes

$$ \bigoplus_{\substack{x-u\x\ne v}}c_{ux}

l(u)\oplus b , $$

and the parity equation at $v$ becomes

$$ \bigoplus_{\substack{x-v\x\ne u}}c_{vx}

l(v)\oplus b . $$

Thus the edge $u-v$ disappears, and the labels at its two endpoints are changed by adding $b$ modulo $2$.

Therefore, after assigning values to a collection of edges, the resulting formula is again a Tseitin formula on the graph obtained by deleting those edges. The new label of a vertex is its old label plus the parity of the values assigned to the deleted edges incident with that vertex.

In the example, the two assignments $\mathbf b$ and $\bar{\mathbf b}$ give two complementary choices for the deleted edges. The resulting graphs $G'$ and $G''$ are precisely the connected components that remain after the corresponding edges are removed, with labels changed according to the rule above. A component whose total label is odd gives an unsatisfiable Tseitin formula; a component whose total label is even gives a satisfiable one.

(b)

Let $C\in\alpha(G)$. Then $C\in\alpha(v)$ for some vertex $v$. Taking

$$ V'={v}, $$

we have

$$ \alpha(V')=\alpha(v)\vdash C, $$

and therefore

$$ \mu(C)\leq 1 . $$

The empty set of axioms cannot imply a non-tautological clause, so

$$ \mu(C)\geq 1 . $$

Hence

$$ \boxed{\mu(C)=1}. $$

Now consider the empty clause $\varepsilon$. Since $\alpha(G)$ is unsatisfiable,

$$ \alpha(V)\vdash\varepsilon, $$

$$ \mu(\varepsilon)\leq |V|. $$

It remains to show that no proper subset of the vertices suffices.

Let $V'\subsetneq V$. Because $G$ is connected, the boundary

$$ \partial V'={c_{uv}:u\in V',v\notin V'} $$

is nonempty. Summing the parity equations for all vertices in $V'$, all internal edge variables cancel and only boundary variables remain:

$$ \bigoplus_{c\in\partial V'}c

\bigoplus_{v\in V'}l(v). $$

Because $\partial V'\neq\varnothing$, one boundary variable can always be chosen after all the others have been assigned so that this equation holds. Once the boundary variables have been fixed, each connected component of the induced subgraph on $V'$ has at least one free edge variable or is attached to the boundary, so the remaining internal variables can be assigned to satisfy all vertex equations.

Therefore $\alpha(V')$ is satisfiable for every proper subset $V'\subsetneq V$. Hence no proper subset can imply the empty clause, and

$$ \boxed{\mu(\varepsilon)=|V|}. $$

(c)

Let

$$ |V'|=\mu(C) $$

and suppose

$$ \alpha(V')\vdash C . $$

We prove that every variable of $\partial V'$ occurs in $C$.

Assume instead that there is a boundary variable

$$ x=c_{uv}\in\partial V' $$

which does not occur in $C$. Without loss of generality,

$$ u\in V',\qquad v\notin V'. $$

Consider the set

$$ W=V'\setminus{u}. $$

We claim that

$$ \alpha(W)\vdash C . $$

Suppose not. Then there exists an assignment satisfying $\alpha(W)$ and falsifying $C$.

We extend this assignment to the variables incident with $u$. The only constraint introduced by adding the vertex $u$ is the parity equation at $u$:

$$ \bigoplus_{z-u}c_{uz}=l(u). $$

Among the incident variables of $u$, the boundary variable $x$ occurs, and $x$ is not present in $C$. We may therefore choose all other incident variables arbitrarily and then choose $x$ so that the parity equation at $u$ holds. Thus the assignment extends to one satisfying $\alpha(V')$.

The value of $C$ is unchanged, because $x$ does not occur in $C$. Hence we have constructed an assignment satisfying $\alpha(V')$ but falsifying $C$, contradicting

$$ \alpha(V')\vdash C . $$

Therefore no boundary variable can be omitted from $C$, and

$$ \boxed{\partial V'\subseteq \operatorname{vars}(C)} . $$

The minimality assumption $|V'|=\mu(C)$ is essential: it prevents us from replacing $V'$ by a smaller set after removing a vertex whose boundary variable is absent from $C$.

(d)

Let $G$ be the nonbipartite cubic Ramanujan graph on $m$ vertices. Suppose that

$$ |V'|=s $$

and

$$ |\partial V'|=t . $$

The expansion hypothesis gives

$$ \frac{s}{s+t}\leq \frac{s/m+8}{9}. $$

Multiplying through,

$$ 9s\leq (s+t)\left(\frac{s}{m}+8\right). $$

Rearranging,

$$ s-\frac{s^2}{m} \leq t\left(\frac{s}{m}+8\right), $$

and therefore

$$ t\geq \frac{s-s^2/m}{s/m+8}

\frac{s(m-s)}{s+8m}. $$

Now take

$$ s\leq \frac m{78}. $$

Then

$$ m-s\geq \frac{77m}{78} $$

and

$$ s+8m\leq \frac m{78}+8m =\frac{625m}{78}. $$

Consequently,

$$ |\partial V'| \geq \frac{s(77m/78)}{625m/78}

\frac{77}{625}s . $$

Thus every nonempty set of at most $m/78$ vertices has a nonempty boundary.

Consider a derivation of the empty clause from $\alpha(G)$. A clause $C$ occurring in such a derivation has a minimal supporting set $V'$ with

$$ |V'|=\mu(C). $$

By part (c), every edge leaving $V'$ must occur in $C$. Therefore, if $V'$ is a proper nonempty set with

$$ |V'|\leq m/78, $$

the clause $C$ still contains a boundary variable.

Hence a clause supported by fewer than $m/78$ vertices cannot be the empty clause. The only way to remove all boundary variables is to reach the full vertex set, because $G$ is connected. The full set gives the contradiction arising from the odd total label.

The expansion estimate therefore guarantees that in the branching construction used for $n(\alpha(G)\vdash\varepsilon)$, one can always continue through the smaller side of the current cut until a contradiction is reached, and no branch requires more than

$$ \frac m{78} $$

vertices.

Therefore,

$$ \boxed{n(\alpha(G)\vdash\varepsilon)\leq \frac m{78}} . $$

$\square$

TAOCP 7.2.2.2 Exercise 245