2
$\begingroup$

In simulating a binary branching random walk, I needed to find a proper way to color each walks, so that we could follow a particle for example from its birth time to the end of the simulation, see figure below.

enter image description here

In this model, each node at time $k$ gives birth to a child and continues its own way. The walk is sampled from a (Galton-Watson) tree with proper weight on the edges. Since the number of child here is constant, we have in fact a binary tree $T$.

Let us number the vertices of $T$ as below: enter image description here

The program generates the walk in the following way. Vertex $1$ is the origin it connects each particle at time $n$ to time $n+1$ and the proper weight. The order of addition from left to right, top to bottom. My coloring convention was as follow: I want the leftmost edges in each of a descendant's to be of the same color than the parent to its ancestor's edge. For example, the path $[1-2-4-8]$ would be the same color, so would $[3-7-14]$. We can easily see that we need $2^n$ (8 in the example) colors to have a walk following this set-up. Suppose we have our colors stored in a vector. Coloring an edges that goes from any vertex to an odd-numbered vertex is easy because you need a new color, but for coloring an edge that goes to an even numbered vertex say $2k$, I found that the proper color was stored at index $f(k)$ in the vector, where $f(k)$ is $$ f(k)=\frac{\left(\frac{k}{gcd(k,2^k)}+1\right)}{2} $$

This is sequence A003602 at OEIS.

What I was wondering is if there would be any way to generalize this coloring method to $k$-ary trees. If I'm right, in a ternary tree, we would have to find such a sequence for $0\equiv \mod 3$ labelled vertex. By brute force, the first term of the sequence would be $1,1,2,3,1,4,5,2,6,7$. Any Ideas?

$\endgroup$
1
  • $\begingroup$ I don't know how to simply generalize your method, but I would do something different. Take any function $f : [0,1] \to \mathtt{color}$ (e.g. use hue), and make the root $0$ (zero), and any child $\mathtt{parent}+2^{-\mathtt{level}}$. What do you think? $\endgroup$
    – dtldarek
    Feb 20, 2013 at 22:19

1 Answer 1

1
$\begingroup$

The method generalizes nicely if you're willing to give up your first-born child.

What $k/\gcd(k,2^k)$ does is to divide out any factors of $2$ in $k$; this is what you want because a factor of $2$ corresponds to a leftward step that doesn't change the colour, so this leads you back to the odd-numbered vertex where this colour originated, and then $+1$ and $/2$ yield the colour index.

If you draw out correspondingly numbered $n$-ary trees, you'll find that what generalizes isn't that the number of the left-most vertex is multiplied by $n$, but the number of the second vertex from the right (which is the same thing for $n=2$). Thus, if you're willing to make the penultimate child heir to the ancestral colour, you can calculate the number of the vertex that gave rise to the colour as $k/\gcd(k,n^k)$, and from that you can obtain the colour index as

$$ \left\lceil\frac{n-1}n\frac k{\gcd(k,n^k)}\right\rceil\;. $$

$\endgroup$
1
  • $\begingroup$ Well, for some reason I had not spot that $m^n$ was the penultimate child in generation $n$ in a $m$-ary tree. $\endgroup$ Feb 21, 2013 at 2:44

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.