= Solution
Write $p_i=\mathbb P(A_i)$. A <strong independence graph> of maximum degree one consists of isolated vertices and disjoint pairs. For a component $C$, let $B$ be the event that all events outside $C$ are avoided. Each $A_i$, $i\in C$, is independent of $B$, since the outside vertices are all nonneighbors. The <union bound> therefore gives
$$
\mathbb P\Bigl(B\cap\bigcap_{i\in C}A_i^c\Bigr)\geq\Bigl(1-\sum_{i\in C}p_i\Bigr)\mathbb P(B).
$$
Remove the components successively. If every $p_i<1/2$, all these factors are positive, including singleton components, so simultaneous avoidance has positive <probability>. Conversely, two complementary events of <probability> $1/2$, joined by one edge, cover the sample space. Consequently \b[$\gamma(1)=1/2$]. The argument does not assume joint independence between entire two-event components.
For higher degrees use a <dependency-degree obstruction on a rooted tree>. Put $d=\Delta-1$ and choose
$$
p>p_*:=\frac{d^d}{(d+1)^{d+1}},\qquad p<1.
$$
On a finite rooted $d$-ary <tree> take independent bits $B_v$ and define $A_v$ to mean that $B_v=1$ and every child bit is zero. The underlying <tree> is a <strong independence graph>: the variables used by $A_v$ are disjoint from all variables used by its nonneighbors. Its maximum degree is at most $d+1$.
Give the leaves success probability $r_0=p$, and, working upwards, use
$$
r_{j+1}=\frac{p}{(1-r_j)^d}
$$
as long as this is less than one. This recursion must reach or exceed one after finitely many steps. Indeed,
$$
\max_{0\leq r\leq1}r(1-r)^d=\frac{d^d}{(d+1)^{d+1}}<p,
$$
so the iterates strictly increase. An infinite sequence staying below one would either converge to a fixed point, contradicting the displayed maximum, or tend to one, in which case its next iterate would exceed one. At the first offending step set the root success probability to one instead of the proposed value. Every nonroot event then has <probability> exactly $p$; the root event has <probability> $(1-r_j)^d\leq p$.
Every configuration contains an occurring event: start at the root, whose bit is one; if its event fails, descend to a child whose bit is one, and repeat. A finite <tree> forces this descent to end at an occurring event. Thus avoidance is impossible. Given any $c>p_*$, choose $p\in(p_*,\min(c,1))$; all event <probabilities> are strictly below $c$. This proves
$$
\boxed{\gamma(\Delta)\leq\frac{(\Delta-1)^{\Delta-1}}{\Delta^\Delta}\quad(\Delta\geq2).}
$$
Back to article page
