11. June 2013

The width of “canonical” trees and of acyclic digraphs


We analyze various parameters of trees coming from prefix codes and from a problem in number theory, namely representing $1$ as a sum of negative powers of a fixed integer base. Asymptotic results are given, for example mean, variance and a central limit theorem for the height and the total path length, respectively, but the main focus of this talk is on the width of such trees. We calculate the mean and show that the width satisfies a certain concentration property. The same method is then used for analyzing the width of acyclic digraphs.