Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  dtldarek Feb 20 '13 at 22:19

1 Answer 1

up vote 1 down vote accepted

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\;. $$

share|improve this answer
    
Well, for some reason I had not spot that $m^n$ was the penultimate child in generation $n$ in a $m$-ary tree. –  Jean-Sébastien Feb 21 '13 at 2:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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