1
$\begingroup$

Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that

(i) Every root-leaf path of $T$ contains at least one edge in $S$;

(ii) For any subset $U$ of the edges of $T$, there holds $$ \Pr( U \subseteq S ) \leq q^{|U|} $$ for some $q = \Theta(1/R)$.

Is it possible to generate $S$ in this manner?

To explain these two conditions, note that if we only want to satisfy condition (ii) for sets $U$ of cardinality one, there is a simple way to do it: select a random integer $J$ uniformly in the range $\{ 1, ..., R \}$, and then set $S$ to be the edges at depth $J$.

Alternatively, if we want to satisfy condition (ii) with a slightly larger value $q = \Theta(\frac{\log n}{R} )$, it is also easy to do it: each edge of $T$ goes into $S$ independently with probability $p = \frac{\log n}{R}$. Note then that with high probability condition (i) is satisfied.

$\endgroup$
1
$\begingroup$

Consider a binary tree of depth $R$ so that $n=2^R$. We will show that in this case, it is impossible to satisfy (i) and (ii) with $q \le 1/8$. A more precise estimate can be obtained using the generating function for Catalan numbers, but the goal is just to show that if (i) and (ii) hold then $q$ is bounded away from zero as $R$ grows; in particular $q=\Theta (1/R)$ is not compatible with (i) and (ii).

The number of minimal edge-cutsets of size $k$ that separate the root from level $R$ is at most the number of full binary trees with $k$ parent nodes, which is less than $4^k$ (It is actually a Catalan number, see [1].) In order to separate the root from the leaves, one of the cutsets must be in $S$ and this event has probability at most $\sum_{k \ge 2} 4^k q^{-k}$ by (ii). In particular, this probability is at most $1/2$ for $q \le 1/8$. Thus to satisfy both (i) and (ii) we must have $q>1/8$.

[1] https://math.stackexchange.com/questions/1944275/rooted-binary-trees-and-catalan-numbers/1944303

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.