Section 7.2.2.2: Satisfiability

Exercise 319. [HM20] Show that $pdc < 1$ implies $p \le (d-1)^{d-1}/d^d$.

Verified: no
Solve time: 5m30s

---

Solution

Let

$$ t=d-1 . $$

Then $t\geq 1$, and the hypothesis becomes

$$ p>\frac{t^t}{(t+1)^{t+1}} . $$

If $p=1$, a graph consisting of a single vertex gives a counterexample, since the corresponding bad event occurs with probability $1$, so the probability of avoiding it is $0$. Assume therefore that

$$ \frac{t^t}{(t+1)^{t+1}}<p<1 . $$

For a graph $G$, Theorem J characterizes $\mathcal R(G)$ in terms of the independence polynomial. Define

$$ Z_G(p)=\sum_I(-p)^{|I|}, $$

where the sum is over all independent sets $I$ of $G$. The characterization states that if

$$ (p,\ldots,p)\in\mathcal R(G), $$

then

$$ Z_H(p)>0 $$

for every induced subgraph $H$ of $G$. Hence it is enough to construct a graph of maximum degree $d$ whose independence polynomial is negative.

Let $T_h$ be the complete rooted $t$-ary tree of height $h$. Every nonroot internal vertex has one parent and $t$ children, so its degree is

$$ t+1=d. $$

The root has degree $t<d$, and therefore

$$ \Delta(T_h)=d . $$

Let $B_h$ be the contribution to $Z_{T_h}(p)$ from independent sets that do not contain the root, and let $A_h$ be the contribution from independent sets that contain the root. Thus

$$ Z_h=A_h+B_h . $$

For the tree of height $0$,

$$ B_0=1, $$

because the empty independent set is the only independent set avoiding the root, and

$$ A_0=-p, $$

because the independent set containing the root contributes $-p$. Hence

$$ Z_0=1-p . $$

For $h\geq 1$, if the root is excluded, each of its $t$ subtrees may contribute any independent set. Therefore

$$ B_h=Z_{h-1}^t . $$

If the root is included, none of its children may be included, and each child subtree contributes only independent sets avoiding its root. Therefore

$$ A_h=-pB_{h-1}^t . $$

Consequently,

$$ Z_h=Z_{h-1}^t-pB_{h-1}^t . $$

Whenever $Z_h\neq0$, define

$$ r_h=\frac{B_h}{Z_h}. $$

Since

$$ Z_h=B_h\left(1-p\left(\frac{B_{h-1}}{Z_{h-1}}\right)^t\right), $$

we obtain

$$ r_h=\frac1{1-pr_{h-1}^t}. \tag{1} $$

The initial value is

$$ r_0=\frac1{1-p}>0 . $$

Consider the function

$$ g(x)=x-px^{t+1}. $$

Its derivative is

$$ g'(x)=1-p(t+1)x^t . $$

The only positive critical point is

$$ x_0=\frac1{(p(t+1))^{1/t}}, $$

and this point gives the maximum value of $g$ on the positive real axis. Substitution gives

$$ g(x_0)

x_0-px_0^{t+1}. $$

From

$$ p(t+1)x_0^t=1, $$

we obtain

$$ px_0^{t+1}=\frac{x_0}{t+1}, $$

and therefore

$$ g(x_0)

\frac{t}{t+1}x_0

\frac{t}{t+1}\frac1{(p(t+1))^{1/t}} . $$

The inequality

$$ g(x_0)<1 $$

is equivalent to

$$ \frac{t^t}{(t+1)^{t+1}}<p . $$

This is exactly the assumed inequality, so

$$ g(x)<1 \tag{2} $$

for every positive $x$.

Suppose that the sequence $(r_h)$ remains defined and positive. For every positive $x$ for which the denominator in (1) is positive,

$$ \frac1{1-px^t}>x $$

is equivalent to

$$ 1>x-px^{t+1}. $$

By (2), this inequality holds for every positive $x$. Applying it with $x=r_{h-1}$ gives

$$ r_h>r_{h-1}. $$

Thus $(r_h)$ is strictly increasing.

If $(r_h)$ were bounded, it would have a finite positive limit $r$. Taking limits in (1) would give

$$ r=\frac1{1-pr^t}. $$

After rearranging,

$$ r-pr^{t+1}=1. $$

This contradicts (2). Therefore $(r_h)$ is unbounded.

Choose $h$ such that

$$ pr_h^t>1 . $$

The recurrence for $Z_{h+1}$ gives

$$ Z_{h+1}

B_{h+1}(1-pr_h^t). $$

The quantity $B_{h+1}=Z_h^t$ is positive, because all previous ratios were defined and positive. The factor

$$ 1-pr_h^t $$

is negative by the choice of $h$. Hence

$$ Z_{h+1}<0 . $$

The graph

$$ G=T_{h+1} $$

therefore satisfies

$$ Z_G(p)<0 . $$

Theorem J implies that a graph with such an independence polynomial cannot have

$$ (p,\ldots,p)\in\mathcal R(G). $$

Since $T_{h+1}$ has maximum degree

$$ t+1=d, $$

this gives a graph of maximum degree $d$ for every

$$ p>\frac{(d-1)^{d-1}}{d^d} $$

such that

$$ (p,\ldots,p)\notin\mathcal R(G). $$

This completes the proof.

∎