1
$\begingroup$

We are given two rooted trees $T_1, T_2$ which have the same depth $d$, and for each leaf there is a path to it of length $d$ from the root. Also, assume the number of children for each node is bounded by $n$. For each level of the tree $i\in \{1,\dots,d\}$ and possible number of children $j\in\{1\dots,n\}$ we draw a number $a_{i,j}\sim U([0,1])$, where all the draws are independent.

Let $P_1$ and $P_2$ be the sets of all paths from leaves to root for $T_1$ and $T_2$ respectively. We compute the following number:

$C_1 = \sum_{\{v_1,\dots,v_d\}\in P_1} \prod_{v_i \in \{v_1,\dots,v_d\}} a_{i,\text{deg}(v_i)}~,$

and we define $C_2$ similarly. In words, we sum all the possible paths from the root to the leaves, and for each path we multiply the numbers $a_{i,j}$ which corresponds to the nodes in the path, where $i$ is the depth of the node and $j$ is its number of children.

I want to show that if the trees $T_1$ and $T_2$ are different (i.e. non-isomorphic), then with probability $1$ over the draws of $a_{i,j}$ also $C_1\neq C_2$.

My take on this is that if in some layer $i$ there is a node $v$ in $T_1$ of degree $j$ and there is no node of degree $j$ in layer $i$ in $T_2$, then certainly $C_1\neq C_2$. This is because the draws are independent, hence conditioning on all the draws except for $a_{i,j}$, we are given that $C_1 = a_{i,j} \cdot c_1 + c_2$ where $c_1$ and $c_2$ are some non-zero constants (w.p 1), and also $C_2$ is a constant, hence $C_1\neq C_2$ w.p 1. My problem is when there is no such node with a different degree.

$\endgroup$
3
  • $\begingroup$ I am not sure I understand completely. What happens with one tree where the root has two children and each of those have three children which are leaves, compared to another tree where the root has three children and each of those have two children which are leaves? $\endgroup$
    – Henry
    Commented Mar 1, 2023 at 10:38
  • $\begingroup$ In your example, the number of children for the roots of is different. We can write $C_1 = a_{1,2} \cdot c_1$ and $C_2 = a_{1,3} \cdot c_2$ where $c_1,c_2$ are some numbers, and $a_{1,2}, a_{1,3}$ are the random draws for a node in layer 1 (i.e. the root) with 2 or 3 children. To see that $C_1 \neq C_2$ we have that the probability of them being equal is the same as the probability of them being equal conditioned on all the random draws except $a_{1,2}, a_{1,3}$, and this probability is zero because $a_{1,2}, a_{1,3}$ are drawn uniformly from [0,1]. $\endgroup$
    – giladude
    Commented Mar 1, 2023 at 11:56
  • 1
    $\begingroup$ It's a minor issue, but some indices are off. If a path from root to leaf has length $d$, then it will have $d+1$ nodes $v_1, v_2, \dots, v_{d+1}$, where $v_1$ is the root and $v_{d+1}$ is the leaf. Probably you want the product to only have $a_{i, \deg(v_i)}$ for $i=1,2,\dots,d$, because $a_{d+1, \deg(v_{d+1})} = a_{d+1,0}$ is undefined. $\endgroup$ Commented Mar 1, 2023 at 15:27

1 Answer 1

1
$\begingroup$

The following two trees $T_1$ and $T_2$ will always have $C_1 = C_2$, because the sets of paths they have, as identified by the degrees of the vertices, are identical. Specifically, there are $6$ paths of type $(2,2,3,0)$ and $4$ paths of type $(2,2,2,0)$, where a path of type $(k_1,k_2,k_3,k_4)$ means that the $i^{\text{th}}$ node visited has $k_i$ children.

enter image description here

(I think this means that $C_1 = C_2 = 6 a_{1,2} a_{2,2} a_{3,3} + 4 a_{1,2} a_{2,2}, a_{3,2}$ but I am not quite sure of the notation.)

However, these two trees are not isomorphic; they can be distinguished by the distance between the two nodes which have $3$ children.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .