Section 7.2.2.2: Satisfiability

Exercise 320. [HM24] Given a lospdependency graph $G$, the occurrence threshold $\rho(G)$ is the smallest value $p$ such that it's sometimes impossible to avoid all events when each event occurs with probability $p$. For example, the Möbius polynomial for the path $P_5$ is $1 - p_1 - p_2 - p_3 + p_1 p_5$; so the occurrence threshold is $\phi^{-2}$, the least $p$ with $1 - 3p + p^2 \le 0$.

a) Prove that the occurrence threshold for $P_n$ is $1/(4\cos^2 \frac{\pi}{n+2})$.

b) What is the occurrence threshold for the cycle graph $C_m$?

Verified: yes
Solve time: 4m56s

---

Solution

Let $\mu(G)$ denote the Möbius polynomial of a graph $G$ with all vertex probabilities equal to $p$. The occurrence threshold is the smallest value of $p$ for which $\mu(G)\leq 0$ can occur.

For the path $P_n$, let

$$ a_n=\mu(P_n). $$

Removing the last vertex of the path gives two cases. If the last vertex is not chosen in an independent set, the contribution is $a_{n-1}$. If it is chosen, the preceding vertex cannot be chosen, and the contribution is $-p a_{n-2}$. Hence

$$ a_n=a_{n-1}-p a_{n-2}. $$

The initial values are

$$ a_0=1,\qquad a_1=1-p. $$

Let $\lambda_+$ and $\lambda_-$ be the roots of

$$ \lambda^2-\lambda+p=0. $$

They satisfy

$$ \lambda_++\lambda_-=1,\qquad \lambda_+\lambda_-=p. $$

The recurrence and initial conditions give

$$ a_n=\frac{\lambda_+^{,n+2}-\lambda_-^{,n+2}} {\lambda_+-\lambda_-}. $$

For $p>1/4$, write

$$ \lambda_\pm=\sqrt p,e^{\pm i\theta}, $$

where

$$ \cos\theta=\frac1{2\sqrt p}. $$

Then

$$ a_n

p^{(n+1)/2} \frac{\sin((n+2)\theta)}{\sin\theta}. $$

The first loss of positivity occurs when the numerator first vanishes. Since $0<\theta<\pi/2$, the smallest possible value is

$$ (n+2)\theta=\pi . $$

Therefore

$$ \theta=\frac{\pi}{n+2}. $$

Using

$$ \cos\theta=\frac1{2\sqrt p}, $$

we obtain

$$ \cos\frac{\pi}{n+2}

\frac1{2\sqrt p}. $$

Squaring and solving for $p$ gives

$$ p=\frac1{4\cos^2\frac{\pi}{n+2}}. $$

For smaller values of $p$, the angle $\theta$ is smaller, so

$$ 0<(n+2)\theta<\pi, $$

and therefore

$$ a_n>0. $$

For the value above, $a_n=0$, and for larger values the sign changes. Hence the occurrence threshold of $P_n$ is

$$ \boxed{\rho(P_n)=\frac1{4\cos^2\frac{\pi}{n+2}}}. $$

For the cycle graph $C_m$, let

$$ b_m=\mu(C_m). $$

The independent sets of $C_m$ either exclude a fixed vertex, giving the contribution from $P_{m-1}$, or include that vertex, in which case its two neighbors are excluded and the remaining contribution is from $P_{m-3}$. Thus

$$ b_m=a_{m-1}-p a_{m-3}. $$

Substituting the expression in terms of $\lambda_+$ and $\lambda_-$ gives

$$ b_m=\lambda_+^m+\lambda_-^m . $$

For $p>1/4$, use the same representation

$$ \lambda_\pm=\sqrt p,e^{\pm i\theta}. $$

Then

$$ b_m

p^{m/2} \left(e^{im\theta}+e^{-im\theta}\right), $$

so

$$ b_m=2p^{m/2}\cos(m\theta). $$

The first zero occurs when

$$ m\theta=\frac{\pi}{2}. $$

Hence

$$ \theta=\frac{\pi}{2m}. $$

Using again

$$ \cos\theta=\frac1{2\sqrt p}, $$

we get

$$ \cos\frac{\pi}{2m}

\frac1{2\sqrt p}. $$

Therefore

$$ p=\frac1{4\cos^2\frac{\pi}{2m}}. $$

For smaller $p$, the corresponding angle satisfies

$$ 0<m\theta<\frac{\pi}{2}, $$

so

$$ \cos(m\theta)>0 $$

and the Möbius polynomial remains positive. At the displayed value it becomes zero, and for larger $p$ it becomes nonpositive. Consequently the occurrence threshold for the cycle is

$$ \boxed{\rho(C_m)=\frac1{4\cos^2\frac{\pi}{2m}}}. $$

This completes the proof.

∎