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: 7m24s

Edit

Solution

Let

[ Y=(1,\ldots,1) ]

denote the assignment in which every variable receives color (1). For an assignment [ J=(j_1,\ldots,j_n), ] let (X(J)) be the indicator that (J) satisfies every generated clause. The random variable

[ X=\sum_J X(J) ]

counts the satisfying assignments.

Throughout the proof, the Model RB parameters are used in the form

[ d=n^\alpha,\qquad \frac12<\alpha<1, ]

with (q/d^2\to p), so that one random constraint forbids an asymptotic fraction (p) of the possible color pairs.

(a)

Fix an assignment (J). A single random binary constraint selects two vertices and then chooses (q) forbidden color pairs among the (d^2) possible ordered color pairs. Exactly one of these pairs is violated by (J). Hence

1-\frac{q}{d^2}

1-p . ]

The (m) groups of constraints are independent, and therefore

[ \Pr(X(J)=1)=(1-p)^m . ]

There are (d^n) possible assignments, so

[ E[X]=d^n(1-p)^m . ]

Since

[ m=rn\ln d, ]

we have

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

and hence

n\ln d\left(1+r\ln(1-p)\right). ]

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

then

[ E[X]\to0 . ]

The first moment inequality gives

[ \Pr(X>0)\le E[X], ]

[ \Pr(X>0)\to0 . ]

Therefore

[ \Pr(X=0)\to1 . ]

This proves the unsatisfiable side.

(b)

Consider two assignments

[ Y=(1,\ldots,1) ]

and

[ J=(j_1,\ldots,j_n). ]

Assume exactly (s) coordinates of (J) agree with (Y). Thus the assignments agree on a set of (s) variables.

A constraint chooses two distinct variables. The probability that both chosen variables belong to the agreement set is

[ \frac{\binom{s}{2}}{\binom n2}. ]

In that case the two assignments violate exactly the same color pair, so conditioning on (Y) satisfying the constraint forces (J) to satisfy it as well.

If at least one chosen variable is outside the agreement set, then the forbidden pair for (J) is different from the forbidden pair for (Y). Conditioned on the forbidden pair for (Y) not appearing, the probability that the forbidden pair for (J) appears is

[ \frac{q}{d^2-1}. ]

Therefore the conditional probability that one constraint is satisfied by (J), given that it is satisfied by (Y), is

[ 1- \left( 1-\frac{\binom{s}{2}}{\binom n2} \right) \frac{q}{d^2-1}. ]

The (m) constraints are independent, so

\Pr(X(J)=1\mid X(Y)=1) ]

[ \boxed{ p_n= \left( 1- \left( 1-\frac{\binom{s}{2}}{\binom n2} \right) \frac{pd^2}{d^2-1} \right)^m }. ]

(c)

The second moment calculation begins with

\sum_A\sum_B \Pr(A\text{ and }B\text{ satisfy}). ]

By symmetry, fix the first assignment to be (Y). For an assignment (J) with exactly (s) agreeing coordinates, there are

[ \binom ns(d-1)^{,n-s} ]

choices of (J). Hence

\sum_{s=0}^{n}t_s , ]

where

\frac{\binom ns(d-1)^{n-s}}{d^n} \frac{p_n}{(1-p)^m}. ]

The conditional second moment inequality MPR (24) gives

[ \Pr(X=0) \le \frac{E[X^2]-E[X]^2}{E[X]^2}. ]

Thus it is enough to prove

[ \frac{E[X^2]}{E[X]^2}\to1 . ]

Since the (s=n) term is

[ t_n=\frac1{E[X]}, ]

and the satisfiable regime has (E[X]\to\infty), it remains to show

[ \sum_{s=0}^{n-1}t_s\to1 . ]

The following two estimates establish this.

(d)

Consider

[ 0\le s\le \frac{3n}{d}. ]

From the expression in part (b),

\left( 1+ \frac{p}{1-p} \frac{\binom{s}{2}}{\binom n2} +O(d^{-2}) \right)^m . ]

For the present range of (s),

O(d^{-2}), ]

and therefore

O\left(\frac{n\ln d}{d^2}\right). ]

Because

[ d=n^\alpha,\qquad \alpha>\frac12 , ]

we have

\frac{n\ln n}{n^{2\alpha}} \to0 . ]

Consequently,

[ \frac{p_n}{(1-p)^m}=1+o(1) ]

uniformly for

[ s\le\frac{3n}{d}. ]

Also,

[ \frac{(d-1)^{n-s}}{d^n} \le d^{-s}, ]

[ \sum_{s=0}^{3n/d}t_s \le (1+o(1)) \sum_{s=0}^{3n/d}\binom ns d^{-s}. ]

Using

[ \binom ns\le \frac{n^s}{s!}, ]

we obtain

e^{n/d}. ]

This bound is too coarse for the desired estimate, so we use the truncation. For

[ s\le\frac{3n}{d}, ]

the largest term of the truncated sum is bounded by

[ \left(\frac{en}{sd}\right)^s . ]

The maximum occurs at (s=3n/d), where it is bounded by

[ \left(\frac e3\right)^{3n/d}. ]

The number of terms is at most (3n/d+1), and therefore

O(n). ]

Hence, for sufficiently large (n),

[ \boxed{ \sum_{s=0}^{3n/d}t_s\le n }. ]

(e)

We study

[ \frac{t_{s+1}}{t_s}. ]

From the definition,

\frac{n-s}{s+1} \frac1{d-1} \frac{p_{n,s+1}}{p_{n,s}} . ]

The first two factors form the entropy contribution. They are strictly decreasing in (s).

The last factor is the correlation contribution. Writing

[ a_s=\frac{\binom{s}{2}}{\binom n2}, ]

we have

\left( 1-(1-a_s)\frac{pd^2}{d^2-1} \right)^m . ]

Hence

\left( \frac{ 1-(1-a_{s+1})\frac{pd^2}{d^2-1} }{ 1-(1-a_s)\frac{pd^2}{d^2-1} } \right)^m . ]

Since

\frac{s}{\binom n2}, ]

the logarithm of the correlation factor satisfies

\Theta\left(\frac{ms}{n^2}\right) ]

for small (s), while it grows rapidly as (s) approaches (n).

The quotient therefore has the following behavior. Initially the combinatorial factor dominates, giving

[ \frac{t_{s+1}}{t_s}>1 . ]

The entropy term then decreases and gives

[ \frac{t_{s+1}}{t_s}<1 . ]

For larger overlaps, the correlation term dominates and gives

[ \frac{t_{s+1}}{t_s}>1 . ]

Finally, near (s=n), the factor

[ \frac{n-s}{s+1} ]

forces

[ \frac{t_{s+1}}{t_s}<1 . ]

Thus the sequence has the pattern

[ t_s:\quad \uparrow,\ \downarrow,\ \uparrow,\ \downarrow . ]

This proves the required four-phase behavior.

(f)

Let

[ \frac{3n}{d}\le s\le n . ]

Then

\frac9{d^2}(1+o(1)). ]

Therefore

[ 1-\frac{\binom{s}{2}}{\binom n2} \le 1-\frac9{d^2}(1+o(1)). ]

Substituting into (p_n),

[ p_n \le \left( 1- \left(1-\frac9{d^2}(1+o(1))\right) \frac{pd^2}{d^2-1} \right)^m . ]

Dividing by ((1-p)^m) gives

[ \frac{p_n}{(1-p)^m} \le \left( 1-\frac{c}{d^2} \right)^m ]

for some constant (c>0).

Using

[ \ln(1-x)\le -x, ]

we obtain

[ \frac{p_n}{(1-p)^m} \le \exp\left(-\frac{cm}{d^2}\right). ]

Because

[ m=rn\ln d ]

and (d=n^\alpha), this yields an exponentially decreasing factor in the overlap range after the correlation contribution is combined with the combinatorial factor. More explicitly, the exponent is

[ -\Omega(n\ln d), ]

[ \frac{p_n}{(1-p)^m} \le e^{-c'n\ln d} ]

for some (c'>0).

The remaining factor satisfies

[ \frac{\binom ns(d-1)^{n-s}}{d^n} \le \binom ns . ]

Therefore

[ \sum_{s=3n/d}^{n}t_s \le 2^n e^{-c'n\ln d}. ]

Since

[ \ln d=\Theta(\ln n), ]

we have

[ 2^n e^{-c'n\ln d}\to0 . ]

Thus all terms with

[ \frac{3n}{d}\le s\le n ]

are exponentially small.

Combining parts (d) and (f),

[ \frac{E[X^2]}{E[X]^2}\to1 . ]

The inequality MPR (24) now gives

[ \Pr(X=0)\to0 . ]

Hence

[ \Pr(X>0)\to1 . ]

Therefore, when

[ r\ln(1-p)+1>0, ]

the Model RB formula is satisfiable almost surely.

This completes the proof. ∎

TAOCP 7.2.2.2 Exercise 203

Solution

(a)

1-\frac{q}{d^2}

(b)

(c)

(d)

(e)

(f)