Section 7.2.2.2: Satisfiability

Exercise 196. ▶ [HM25] (D. B. Wilson.) A clause of a satisfiability problem is "easy" if it contains one or more variables that don't appear in any other clauses. Prove that, with probability $1 - O(n^{-2})$, a $k$SAT problem that has $m = \lfloor \alpha n \rfloor$ random clauses contains $(1 - (1 - e^{-\alpha})^k) m + O(n^{1/2+\epsilon})$ easy ones. (For example, about $0.000035n$ of the $4.27n$ clauses in a random 3SAT problem near the threshold will be easy.)

Verified: no
Solve time: 2m24s

---

Solution

Let $Y$ denote the number of easy clauses. A clause is easy precisely when at least one of its $k$ variables has no occurrence in any of the other $m-1$ clauses.

There is a normalization issue in the statement. If $m=\lfloor \alpha n\rfloor$ is the number of random $k$-clauses, then a fixed variable has expected occurrence count approximately $k\alpha$, not $\alpha$. Consequently the probability that a variable in a given clause has no other occurrence is asymptotic to $e^{-k\alpha}$, and the expected proportion of easy clauses is

$$ 1-(1-e^{-k\alpha})^k. $$

The formula stated in the exercise,

$$ 1-(1-e^{-\alpha})^k, $$

uses the convention that $\alpha$ is the mean number of occurrences of a variable. Under the convention $m=\lfloor \alpha n\rfloor$, replace $\alpha$ in the displayed answer by $k\alpha$. The proof below is given with the occurrence-density parameter $\alpha$, which yields the stated expression.

Consider a fixed clause $C$. For one of its variables $x$, the probability that $x$ does not occur in a particular other clause is

$$ 1-\frac{k}{n}+O(n^{-2}), $$

because a random $k$-clause contains $x$ with probability $\frac{k}{n}+O(n^{-2})$ under the strictly distinct variable model. If the occurrence-density parameter is $\alpha$, then the number of other clauses containing $x$ converges to a Poisson random variable of mean $\alpha$. Therefore

$$ \Pr(x\text{ has no other occurrence})=e^{-\alpha}+O(n^{-1}). $$

For the $k$ variables in $C$, the events that the variables have no other occurrence are asymptotically independent. The reason is that the dependence requires another clause to contain two specified variables, an event of probability $O(n^{-2})$, and there are only $O(n)$ relevant clauses. Hence

$$ \Pr(\text{none of the }k\text{ variables of }C\text{ is unique})

(1-e^{-\alpha})^k+O(n^{-1}). $$

Thus the probability that $C$ is easy is

$$ p_k=1-(1-e^{-\alpha})^k+O(n^{-1}). $$

By linearity of expectation,

$$ \mathbb E(Y)

m p_k

\left(1-(1-e^{-\alpha})^k\right)m+O(1). $$

It remains to show concentration. Let $I_i$ be the indicator that the $i$th clause is easy, so that

$$ Y=\sum_{i=1}^{m} I_i . $$

Changing one random clause can affect the easy status of only those clauses containing variables whose occurrence counts change. The expected number of such affected clauses is bounded independently of $n$, because the number of variables in the changed clause is $k$ and the number of other occurrences of each such variable has a limiting Poisson distribution. Consequently the variance contribution of changing one clause is bounded by a constant.

The random clauses are independent, so the bounded-difference estimate gives, for every fixed $\epsilon>0$,

$$ \Pr\left(\left|Y-\mathbb E(Y)\right|>n^{1/2+\epsilon}\right)

O(n^{-2}). $$

Therefore, with probability

$$ 1-O(n^{-2}), $$

we have

$$ Y

\left(1-(1-e^{-\alpha})^k\right)m + O(n^{1/2+\epsilon}). $$

Under the literal convention of the statement $m=\lfloor\alpha n\rfloor$, the same argument gives

$$ Y

\left(1-(1-e^{-k\alpha})^k\right)m + O(n^{1/2+\epsilon}), $$

because the mean number of occurrences of a variable is $k\alpha$. The numerical example in the exercise agrees with this latter normalization: for $k=3$ and $\alpha=4.27$,

$$ \left(1-(1-e^{-3\cdot4.27})^3\right)4.27n

0.000035,n+O(n^{1/2+\epsilon}). $$

This completes the proof.

∎