Exercise 315. [M18] What value of $p$ is appropriate in Theorem J when $d = 1$?

Verified: yes
Solve time: 4m03s

Solution

Theorem J states that if every vertex of $G$ has degree at most $d$, then the symmetric probability vector $(p,\ldots,p)$ belongs to $R(G)$ when

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

for $d>1$. The exercise asks for the missing case $d=1$, which must be handled directly from Theorem L.

When $d=1$, every vertex of $G$ has at most one neighbor. In Theorem L we need a value $\theta$ satisfying

$$ p=\theta\prod_{i\mathbin{-}j\text{ in }G}(1-\theta_j). $$

Using the symmetric choice $\theta_i=\theta$ for every vertex, each vertex has at most one factor in the product. Therefore the required condition is

$$ p\leq \theta(1-\theta). $$

The largest possible value of the right-hand side occurs when

$$ \frac{d}{d\theta}\bigl(\theta(1-\theta)\bigr)=1-2\theta=0, $$

$$ \theta=\frac12 . $$

Substitution gives

$$ \theta(1-\theta)=\frac12\left(1-\frac12\right)=\frac14 . $$

Hence every graph of maximum degree $1$ satisfies the hypothesis of Theorem L whenever

$$ p\leq \frac14 . $$

The value $\frac14$ is also the limiting value suggested by the formula in Theorem J, since

$$ \lim_{d\to1^+}\frac{(d-1)^{d-1}}{d^d}

\lim_{d\to1^+}(d-1)^{d-1}d^{-d} =1, $$

but that expression does not describe the sharp condition for $d=1$. The direct application of Theorem L gives the correct bound.

Therefore the appropriate value of the parameter in Theorem J when $d=1$ is

$$ \boxed{p=\frac14}. $$