Theoretical Statistics and Mathematics Unit, ISI Delhi

April 5, 2017 (Wednesday) ,
3:30 PM at Webinar

Speaker:
Rahul Roy,
ISI Delhi

Title:
Howard's law for binary and related random trees

Abstract of Talk

The Horton-Strahler order of vertices of a rooted binary tree is given iteratively as follows: \begin{itemize} \item[a)] the order of an end-vertex of a leaf is 1, \item[b)] the order $i$ of a vertex $v$ is given by the orders $j$ and $k$ of the two neighbouring vertices in the two sub-branches of $v$, viz., $$i = \begin{cases} \max\{j,k\} & \text{if } j \neq k\\ j + 1 & \text{if } j=k. \end{cases} $$ \end{itemize} Let $N_i$ be the number of vertices of order $i$. For a uniformly chosen random binary tree on $n$ vertices among the class of all such binary trees, Shreve (1966) observed empirically that the ratio $\frac{N_i}{N_{i+1}}$ (suitably interpreted) converges to $4$ as $n \to \infty$. This convergence to a constant is known as Horton's law.

We discuss known results for the critical branching process tree (Burd, Waymire and Winn 2000) and present some conjectures for the random tree obtained from the space-time graphical representation of a system of $1$-dimensional coalescing simple symmetric random walks.