# A binary tree in 3-ary tree

We have an infinite $3$-ary tree, with root $R$. In coloring $C(p)$ each edge is black with probability $p$ and white with probability $1 - p$, and edges are independent.

Show that there is a $p^*$ where $0 < p^* < 1$ such that the graph with coloring $C(p)$ where $p$ is greater than $p^*$ has an infinite black binary sub-tree with probability $1$ and a graph with coloring $C(p)$ where $p$ is less than $p^*$ has an infinite black binary sub-tree with probability $0$.

-
The first "less than" should be "greater than"? (Also, please use $\TeX$ for math formatting by enclosing math in dollar signs; single dollar signs for inline formulas and double dollar signs for displayed equations.) – joriki Sep 29 '12 at 7:50

The entire infinite tree contains an infinite binary tree iff at least one of the infinite trees rooted at the children of the root contains one. Thus the probability $q$ for the tree to contain an infinite binary tree satisfies
$$q=1-(1-q)^3\;,$$
with solutions $0$, $1$ and $2$. Thus the only solutions in $[0,1]$ are $0$ and $1$. It's clear that $q$ is monotonic in $p$. It follows that there must be some $p^*$ at which $q$ switches from $0$ to $1$.
Nice. Do you know whether anything is known about the magnitudes of $p^*$ and $\hat p$? – Brian M. Scott Sep 29 '12 at 8:25
@Brian: I removed the part about $\hat p$; it was wrong since it didn't take into account that there need to be edges between the root and the children that are roots of infinite binary trees. I don't know anything about the magnitude of $p^*$, but I'm thinking about it. – joriki Sep 29 '12 at 8:50