Return to Question

Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching from any root-connected node. We establish an inductive base case, so that $T(0,0)$ contains the root node only.

$T(1,0)$ and $T(0,1)$ trivially has path cardinality $\aleph_0$ (*) . $T(1,1)$, the infinite complete binary tree, trivially has Continuum path cardinality.

$T(a,b)$ is finite for $a+b<1$.

$T(a,b)$ has path cardinality $\aleph_0$ for any $a+b=1$.

Now, is it then true that, $T(a,b)$ has Continuum path cardinality for $a+b>1$?

Intuitively this seems to be the case; Consider for example $T(1,\epsilon )$, for an infinitesimal value $\epsilon$. On average for every $1/ \epsilon$ left-most nodes there is a right-branch. For each occurrence of a right branching node, we contract the graph, deleting all intermittent nodes which produced no right branch, constructing a new graph node, which branches both left and right. By induction we can then show that $T(1,e)$ is isomorphic to $T(1,1)$, and therefore has Continuum path cardinality. It seems a similar argument can be used for any $T(a,b)$ with $a+b>1$. Apologies if this is trivial. Does anyone know of any relevant references on path cardinality for random sub-graphs of the infinite binary tree?

(*) path cardinality of $T$ is short for the cardinality of the set of all paths in $T$.

Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching from any root-connected node. We establish an inductive base case, so that $T(0,0)$ contains the root node only.

$T(1,0)$ and $T(0,1)$ trivially has path cardinality $\aleph_0$ (*) . $T(1,1)$, the infinite complete binary tree, trivially has Continuum path cardinality.

$T(a,b)$ is finite for $a+b<1$.

$T(a,b)$ has path cardinality $\aleph_0$ for any $a+b=1$.

Now, is it then true that, $T(a,b)$ has Continuum path cardinality for $a+b>1$?

Intuitively this seems to be the case; Consider for example $T(1,\epsilon )$, for an infinitesimal probability $\epsilon$. On average for every $1/ \epsilon$ left-most nodes there is a right-branch. For each occurrence of a right branching node, we contract the graph, deleting all intermittent nodes which produced no right branch, constructing a new graph node, which branches both left and right. By induction we can then show that $T(1,\epsilon)$ is isomorphic to $T(1,1)$, and therefore has Continuum path cardinality. It seems a similar argument can be used for any $T(a,b)$ with $a+b>1$. Apologies if this is trivial. Does anyone know of any relevant references on path cardinality for random sub-graphs of the infinite complete binary tree?

(*) path cardinality of $T$ is short for the cardinality of the set of all paths in $T$.