Section 7.2.2.2: Satisfiability

Exercise 318. [HM27] (J. B. Shearer.) Prove that Theorem J is the best possible result of its kind: If $p > (d-1)^{d-1}/d^d$ and $d > 1$, there is a graph $G$ of maximum degree $d$ for which $(p, \ldots, p) \notin \mathcal{R}(G)$. Hint: Consider complete $t$-ary trees, where $t = d - 1$.

Verified: yes
Solve time: 9m06s

---

Setup

Let $t=d-1$. The hypothesis is

$$ p>\frac{(d-1)^{d-1}}{d^d}=\frac{t^t}{(t+1)^{t+1}}, $$

where $t\geq 1$.

For a graph $G$, Shearer's region $\mathcal R(G)$ is characterized by the independent-set polynomial appearing in Theorem J. In particular, if

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

where the sum is over all independent sets $I$ of $G$, then a necessary condition for

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

is that every induced subgraph $H$ of $G$ satisfies

$$ Z_H(p)>0. $$

Therefore it suffices to construct, for every admissible $p$, a graph of maximum degree $d$ whose independent-set polynomial is nonpositive.

Let $T_h$ denote the complete rooted $t$-ary tree of height $h$. Thus every nonleaf vertex has exactly $t=d-1$ children. Every nonroot nonleaf vertex has one parent and $t$ children, so its degree is $t+1=d$, while the root has degree $t<d$. Hence every $T_h$ has maximum degree $d$.

Solution

For $T_h$, define

$$ B_h $$

to be the independent-set polynomial contribution from independent sets that do not contain the root, and define

$$ A_h $$

to be the contribution from independent sets that contain the root. Let

$$ Z_h=A_h+B_h. $$

For the tree of height $0$, there is only one vertex, so

$$ B_0=1, $$

and

$$ A_0=-p. $$

Hence

$$ Z_0=1-p. $$

For $h\geq 1$, an independent set not containing the root is obtained by choosing independently any independent set in each of the $t$ subtrees below the root. Therefore

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

If the root is included, none of its children may be included, so 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 . $$

Introduce the ratio

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

whenever $Z_h\neq0$. Since

$$ Z_h=B_h-pB_{h-1}^t, $$

we obtain

$$ Z_h

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

and hence

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

Initially,

$$ r_0=\frac{B_0}{Z_0} =\frac1{1-p}. $$

We show that the sequence in (1) cannot remain finite and positive for all $h$.

Suppose that $r_h$ remains positive for all $h$. For any positive $x$ for which the denominator in (1) is positive,

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

is equivalent to

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

Define

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

The maximum of $g$ on the positive real axis occurs where

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

so

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

At this value,

$$ g(x)

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

The inequality

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

is equivalent to

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

This is exactly our hypothesis. Therefore

$$ g(x)<1 $$

for every positive $x$, and consequently

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

whenever the denominator is positive.

Applying this inequality to $x=r_{h-1}$ gives

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

for every $h$ for which the sequence is defined.

The sequence $(r_h)$ is therefore strictly increasing. If it were bounded, it would have a finite limit $r$, and taking limits in (1) would give

r=\frac1{1-pr^t}. ] Equivalently,

pr^{t+1}-r+1=0,

$$ or $$

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

$$ This contradicts the inequality already proved that $$

x-px^{t+1}<1

for every positive $x$. Hence $(r_h)$ is unbounded. Choose $h$ large enough that

pr_h^t>1.

$$ Then from $$

Z_{h+1}=B_{h+1}(1-pr_h^t),

and the positivity of $B_{h+1}$, we obtain

Z_{h+1}<0.

Thus the complete $t$-ary tree $T_{h+1}$ has independent-set polynomial

Z_{T_{h+1}}(p)<0.

By the characterization of $\mathcal R(G)$ in Theorem J, a graph whose independent-set polynomial is nonpositive cannot satisfy

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

$$ Taking $$

G=T_{h+1},

$$ we have constructed a graph of maximum degree $$

t+1=d

$$ such that $$

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

$$ Therefore every value $$

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

$$ lies outside the universal range guaranteed by Theorem J. This completes the proof. ∎ $$