= Dependency-degree obstruction on a rooted tree
{title2=$p_d=d^d/(d+1)^{d+1}$}
Let $B_v$ be independent <Bernoulli random variables> on a rooted $d$-ary <tree>, and put $A_v=\{B_v=1,\ B_w=0\text{ for every child }w\}$. Events at nonadjacent vertices use disjoint variables, giving a <dependency graph of events> of maximum degree $d+1$. Assign leaf success probability $p$ and successive probabilities $r_{j+1}=p/(1-r_j)^d$. If $p>\max_{0\leq r\leq1}r(1-r)^d=p_d$, the recursion eventually reaches one. Set the final root success probability to one. Each event has probability at most $p$, but following success vertices down from the root must reach an occurring event. Thus the bad events cover the sample space. This gives an upper bound for uniform avoidance thresholds without assuming a converse to the <Lovász local lemma>.
Back to article page
