Exercise 317. ▶ [M26] Let $\alpha(G) = \Pr(\bar{A}_1 \cap \cdots \cap \bar{A}_m)$ under the assumptions of (133), when $p_i = p = (d-1)^{d-1}/d^d$ for $1 \le i \le m$ and every vertex of $G$ has degree at most $d > 1$. Prove, by induction on $m$, that $\alpha(G) > 0$ and that $\alpha(G) \ge \frac{d-1}{d} \alpha(G \setminus v)$ when $v$ has degree $< d$.

Verified: yes
Solve time: 9m05s

Setup

Let $G$ be the dependency graph from (133), with vertices corresponding to the events $A_1,\ldots,A_m$. Assume that

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

for all $i$, and that every vertex of $G$ has degree at most $d$, where $d>1$. Define

$$ \alpha(G)=\Pr(\bar A_1\cap\cdots\cap\bar A_m). $$

The induction will prove the following statement for every such graph with fewer than $m$ vertices:

$$ \alpha(G)>0, $$

and if $v$ has degree less than $d$, then

$$ \alpha(G)\geq\frac{d-1}{d}\alpha(G\setminus v). $$

A consequence needed during the induction is the following estimate. If a graph $H$ has maximum degree at most $d-1$, then

$$ \alpha(H)\geq\left(\frac{d-1}{d}\right)^{|H|}. $$

This follows from the deletion inequality, because every vertex of $H$ has degree less than $d$.

Solution

The proof is by induction on the number $m$ of vertices.

For $m=0$, there are no events, and therefore

$$ \alpha(G)=1>0. $$

The deletion inequality has no instance to check.

Assume the result holds for all graphs with fewer than $m$ vertices, and let $G$ have $m$ vertices. Let $v$ be a vertex of $G$, and define

$$ B=\bigcap_{u\neq v}\bar A_u . $$

Then

$$ \alpha(G)=\Pr(B)\Pr(\bar A_v\mid B), $$

and

$$ \Pr(B)=\alpha(G\setminus v). $$

Let $N(v)$ be the set of neighbors of $v$. The dependency condition in (133) says that $A_v$ is independent of the collection of events indexed by vertices outside $N(v)\cup{v}$. Hence

$$ \Pr(A_v\mid B)

\Pr\left(A_v\mid\bigcap_{u\in N(v)}\bar A_u\right). $$

The numerator of the conditional probability satisfies

$$ \Pr\left(A_v\cap\bigcap_{u\in N(v)}\bar A_u\right)\leq p, $$

$$ \Pr(A_v\mid B) \leq \frac{p} {\Pr\left(\bigcap_{u\in N(v)}\bar A_u\right)}. $$

Let $H$ be the subgraph induced by $N(v)$. Every vertex of $H$ has degree at most $d-1$, because each vertex in $N(v)$ is adjacent to $v$ in $G$. Therefore the auxiliary estimate gives

$$ \alpha(H)

\Pr\left(\bigcap_{u\in N(v)}\bar A_u\right) \geq \left(\frac{d-1}{d}\right)^{|N(v)|}. $$

Suppose first that $\deg(v)<d$. Then

$$ |N(v)|\leq d-1, $$

and because $(d-1)/d<1$,

$$ \Pr\left(\bigcap_{u\in N(v)}\bar A_u\right) \geq \left(\frac{d-1}{d}\right)^{d-1}. $$

Consequently,

$$ \Pr(A_v\mid B) \leq \frac{\frac{(d-1)^{d-1}}{d^d}} {\left(\frac{d-1}{d}\right)^{d-1}}. $$

The denominator equals

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

$$ \Pr(A_v\mid B)\leq\frac1d. $$

Hence

$$ \Pr(\bar A_v\mid B)\geq1-\frac1d=\frac{d-1}{d}. $$

Therefore,

$$ \alpha(G)

\alpha(G\setminus v)\Pr(\bar A_v\mid B) \geq \frac{d-1}{d}\alpha(G\setminus v), $$

which proves the required deletion inequality.

It remains to prove $\alpha(G)>0$. If $G$ has a vertex $v$ with degree less than $d$, the deletion inequality and the induction hypothesis give

$$ \alpha(G)\geq \frac{d-1}{d}\alpha(G\setminus v)>0. $$

Now consider the remaining case. Every vertex of $G$ has degree exactly $d$. Choose any vertex $v$. The graph $G\setminus v$ has fewer than $m$ vertices, so by the induction hypothesis,

$$ \alpha(G\setminus v)>0. $$

It remains to prove that

$$ \Pr(\bar A_v\mid B)>0. $$

The neighborhood $N(v)$ has exactly $d$ vertices and its induced graph has maximum degree at most $d-1$. Thus

$$ \Pr\left(\bigcap_{u\in N(v)}\bar A_u\right) \geq \left(\frac{d-1}{d}\right)^d. $$

If $d>2$, then

$$ \Pr(A_v\mid B) \leq \frac{\frac{(d-1)^{d-1}}{d^d}} {\left(\frac{d-1}{d}\right)^d}

\frac1{d-1} <1. $$

Therefore

$$ \Pr(\bar A_v\mid B)>0, $$

and hence

$$ \alpha(G)>0. $$

It remains to handle $d=2$. In this case

$$ p=\frac14. $$

The vertex $v$ has exactly two neighbors, so the graph induced by $N(v)$ has two vertices and maximum degree at most $1$. Each vertex of this induced graph has degree less than $d=2$, so the deletion inequality already proved for smaller graphs applies. For a single vertex $w$,

$$ \alpha({w})=\Pr(\bar A_w)=1-p=\frac34. $$

Deleting one vertex from the two-vertex graph gives

$$ \alpha(H)\geq\frac12\cdot\frac34=\frac38. $$

Therefore,

$$ \Pr\left(\bigcap_{u\in N(v)}\bar A_u\right)\geq\frac38>\frac14=p. $$

Using the conditional probability estimate,

$$ \Pr(A_v\mid B) \leq \frac{p} {\Pr\left(\bigcap_{u\in N(v)}\bar A_u\right)} < 1. $$

Thus

$$ \Pr(\bar A_v\mid B)>0, $$

and again

$$ \alpha(G)=\alpha(G\setminus v)\Pr(\bar A_v\mid B)>0. $$

The induction establishes both required statements for every graph with maximum degree at most $d$.

This completes the proof.

∎

TAOCP 7.2.2.2 Exercise 317