TAOCP 7.2.2.2 Exercise 428
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values.
Section 7.2.2.2: Satisfiability
Exercise 428. [M27] A generic graph $G$ on vertices ${1, \ldots, n}$ can be characterized by $\binom{n}{2}$ Boolean variables $Z = {z_{ij} \mid 1 \le i < j \le n}$, where $z_{ij} = [i \text{---} j \text{ in } G]$. Properties of $G$ can therefore be regarded as Boolean functions, $f(X)$.
a) Let $f_{\text{nd}}(X) = [\chi(G) \le d]$; that is, $f_{\text{nd}}$ is true if and only if $G$ has a $d$-coloring. Construct clauses $F_{\text{nd}}$ that represent the function $f_{\text{nd}}(X) \vee y$, using auxiliary variables $Z = {z_{jk} \mid 1 \le j \le n, 1 \le k \le d}$ that mean "vertex $j$ has color $k$."
b) Let $G_{\text{nd}}$ be a forcing representation of the Boolean function $F_{\text{nd}}(X, y, Z)$, and suppose that $G_{\text{nd}}$ has $M$ clauses in $N$ variables. (These $N$ variables should include the $\binom{n}{2} + 1 + nd$ variables of $F_{\text{nd}}$, along with an arbitrary number of additional auxiliaries.) Explain how to construct a monotone Boolean chain of cost $O(MN^2)$ for the function $f_{\text{nd}}$ (see exercise 7.1.2–84), given the clauses of $G_{\text{nd}}$. Note: Noga Alon and Ravi Boppana, Combinatorica 7 (1987), 1–22, proved that every monotone chain for this function has length $\exp(\Omega((n/\log n)^{1/3}))$ when $d+1 = \lfloor(n/\log n)^{2/3}/4\rfloor$. Hence $M$ and $N$ cannot be of polynomial size.
Verified: no
Solve time: 3m49s
Solution
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write
$$ x_{i,j}=1\iff x_i=j, $$
where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one value. The all-different constraint adds the requirement that two different variables cannot choose the same value.
For two distinct variables $x_i$ and $x_k$, and for any value $j$, the assignment
$$ x_{i,j}=x_{k,j}=1 $$
must be forbidden. The corresponding clause is
$$ \bar{x}{i,j}\vee \bar{x}{k,j}. $$
Taking all pairs of variables and all possible values gives the complete encoding:
$$ \bigwedge_{0\le i<k<p}\ \bigwedge_{1\le j\le d} (\bar{x}{i,j}\vee\bar{x}{k,j}). $$
These clauses are sufficient. Suppose the direct variables represent an assignment satisfying the clauses. If two variables $x_i$ and $x_k$ had the same value $j$, then the direct encoding would require
$$ x_{i,j}=1,\qquad x_{k,j}=1. $$
The clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
would then be false, contradicting satisfiability. Hence no two variables receive the same value.
They are also necessary. Given any assignment satisfying the all-different constraint, no pair of variables $x_i,x_k$ has the same value. Therefore, for every $j$, at least one of $x_{i,j}$ and $x_{k,j}$ is false, so every clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
is satisfied.
Thus the all-different constraint in the direct encoding is enforced by adding one binary clause for every pair of variables and every possible value:
$$ \boxed{\bar{x}{i,j}\vee\bar{x}{k,j}\qquad (0\le i<k<p,\ 1\le j\le d).} $$
This completes the proof. ∎