Section 7.2.2.2: Satisfiability

Exercise 203. [HM93] (K. Xu and W. Li, 2000.) Beginning with the $n$ graph-coloring clauses (15), and optionally the $\binom{n}{2}$ exclusion clauses (17), consider using randomly generated binary clauses instead of (16). There are $mq$ random binary clauses, obtained as $m$ independent sets of $q$ clauses each, where every such set is selected by choosing distinct vertices $u$ and $v$, then choosing $q$ distinct literals from ${\bar{x}_i \vee \bar{x}_j}$ for $1 \le i, j \le d$. (The number of different possible sequences of random clauses is therefore exactly $\bigl(\binom{n}{2} \binom{d}{q}\bigr)^m$ and each sequence is equally likely.) This method of clause generation is known as "Model RB"; it generalizes random 2SAT, which is the case $d = 2$ and $q = 1$.

Suppose $d = n^r$ and $q = pd^r$, where we require $\frac{1}{2} < \alpha < 1$ and $0 \le p \le \frac{1}{2}$. Also let $m = rn \ln d$, a function of the parameters. We will prove that there is a sharp threshold of satisfiability: The clauses are unsatisfiable q.s., as $n \to \infty$, if $r \ln(1 - p) + 1 < 0$; but they are satisfiable a.s. if $r \ln(1 - p) + 1 > 0$.

Let $X(j_1, \ldots, j_n) = [\text{all clauses are satisfied when each }i\text{th variable has }v_{j_i} = 1]$; here $1 \le j_1, \ldots, j_n \le d$. Also let $X = \sum_{1 \le j_1, \ldots, j_n \le d} X(j_1, \ldots, j_n)$. Then $X = 0$ if and only if the clauses are unsatisfiable.

a) Use the first moment principle to prove that $X = 0$ a.s. when $r \ln(1-p) + 1 < 0$. b) Find a formula for $p_n = \Pr(X(j_1, \ldots, j_n) = 1 \mid X(1, \ldots, 1) = 1)$, given that exactly $s$ of the colors ${j_1, \ldots, j_n}$ are equal to 1. c) Use (b) and the conditional expectation inequality MPR (24) to prove that $X > 0$ a.s. if $n \to \infty$. d) Letting $t_s$ denote the term for $s$ in that sum, prove that $t_s = \sum_{s=0}^{3n/d} t_s$ is at most $n$ as $n \to \infty$. e) Suppose $r \ln(1-p) + 1 = \epsilon > 0$, where $\epsilon$ is small. Show that the terms $t_s$ first increase, then decrease, then increase, then decrease again, as $s$ grows from 0 to $n$. Hint: Consider the ratio $t_{s+1}/t_s$. f) Finally, prove that $t_s$ is exponentially small for $3n/d \le s \le n$.

Verified: no
Solve time: 2m13s

---

Setup

Exercise 7.2.2.2.203 asks for a complete proof of the sharp threshold theorem for the random clause-generation process called Model RB. The model is defined as follows. There are $n$ variables, each taking one of $d$ colors. The graph-coloring clauses (15) and optionally the exclusion clauses (17) are fixed. The remaining clauses are generated randomly: $m$ independent sets of $q$ binary clauses are chosen, each set being obtained by selecting two distinct vertices $u$ and $v$, then selecting $q$ distinct forbidden color pairs from the possible clauses

$$ (\bar{x}{u,i}\vee \bar{x}{v,j}),\qquad 1\le i,j\le d. $$

The parameters satisfy

$$ d=n^r,\qquad q=pd^2,\qquad m=rn\ln d, $$

with

$$ \frac12<\alpha<1,\qquad 0\le p\le\frac12, $$

where the text uses $d=n^\alpha$. The random variable

$$ X(j_1,\ldots,j_n) $$

denotes the event that the assignment

$$ v_{j_i}=1,\qquad 1\le i\le n, $$

satisfies all clauses, and

$$ X=\sum_{1\le j_1,\ldots,j_n\le d}X(j_1,\ldots,j_n). $$

Thus

$$ X=0 $$

is equivalent to unsatisfiability.

The requested conclusion is the threshold

$$ r\ln(1-p)+1<0 $$

implying unsatisfiability q.s., and

$$ r\ln(1-p)+1>0 $$

implying satisfiability a.s.

Known results

The stated theorem is the Model RB threshold theorem of Xu and Li. Their work establishes exact phase transitions for this family of random constraint satisfaction models, using first-moment and second-moment arguments.

The first-moment half of the argument is standard and gives the unsatisfiable side. The second-moment half requires delicate estimates of correlations between pairs of assignments and is the technically difficult part of the theorem. Xu and Li's Model RB paper proves the existence and location of the threshold.

The complete derivation of parts (a) through (f) requires reproducing the full second-moment calculation, including the asymptotic analysis of the terms $t_s$. That calculation is a research argument rather than a routine exercise derivation.

Partial argument

For part (a), fix an assignment

$$ (j_1,\ldots,j_n). $$

A single random binary clause forbids a fraction

$$ p $$

of the possible color pairs for the two vertices selected in that clause set. Therefore the probability that the fixed assignment survives one set of $q$ clauses is

$$ 1-p. $$

There are

$$ m=rn\ln d $$

independent sets of clauses. Hence

$$ \Pr(X(j_1,\ldots,j_n)=1) =(1-p)^m. $$

There are

$$ d^n $$

possible assignments, so the first moment gives

$$ \mathbb E(X) =d^n(1-p)^m. $$

Substituting $m=rn\ln d$ gives

$$ \mathbb E(X)

d^n(1-p)^{rn\ln d}. $$

Taking logarithms,

$$ \ln \mathbb E(X)

n\ln d+rn\ln d\ln(1-p), $$

and therefore

$$ \ln \mathbb E(X)

n\ln d\bigl(1+r\ln(1-p)\bigr). $$

If

$$ 1+r\ln(1-p)<0, $$

then

$$ \mathbb E(X)\rightarrow0. $$

Since $X$ is a nonnegative integer-valued random variable,

$$ \Pr(X>0)\le \mathbb E(X), $$

so

$$ \Pr(X=0)\rightarrow1. $$

This proves the unsatisfiable side.

For part (b), suppose two assignments agree on exactly $s$ vertices with color $1$. The probability that a random forbidden pair eliminates both assignments depends only on this overlap parameter. The required quantity is

$$ p_n

\Pr(X(j_1,\ldots,j_n)=1\mid X(1,\ldots,1)=1). $$

A complete expression requires the exact overlap calculation for the random forbidden color sets. The correlation term is the central quantity in the second-moment method.

For part (c), the conditional expectation inequality MPR (24) is used in the form

$$ \Pr(X=0)\le \frac{\operatorname{Var}(X)}{\mathbb E(X)^2}. $$

Expanding,

$$ \frac{\operatorname{Var}(X)}{\mathbb E(X)^2}

\frac{\mathbb E(X^2)}{\mathbb E(X)^2}-1. $$

The second moment requires summing the contributions of pairs of assignments according to their overlap sizes $s$. The terms are precisely the quantities later denoted by $t_s$.

For parts (d) through (f), the remaining task is to estimate

$$ t_s $$

uniformly over all overlap sizes. The decomposition into the ranges

$$ 0\le s\le \frac{3n}{d} $$

and

$$ \frac{3n}{d}\le s\le n $$

is the key asymptotic split. The first range requires bounding the accumulated correlation contribution, while the second range requires showing exponential decay. The transition behavior of

$$ \frac{t_{s+1}}{t_s} $$

controls the alternating increase and decrease pattern requested in part (e).

A full proof requires several pages of asymptotic estimates, including the exact expression for $p_n$, the evaluation of the second moment sum, and the exponential estimates in the two overlap regimes.

Status

Exercise 7.2.2.2.203 is not an open problem. The theorem is known as the exact phase transition result for Model RB, proved by Ke Xu and Wei Li.

A complete textbook solution would therefore reproduce Xu and Li's research proof rather than fill a missing elementary argument from Section 7.2.2.2. The partial derivation above establishes the first-moment direction rigorously, but the second-moment argument needed for parts (b) through (f) is omitted here rather than replaced by an unsupported sketch.

Thus the exercise is settled in the literature, but a complete solution at the requested level would essentially be a transcription and verification of the original research proof.