Understanding the size of phylogenetic network classes and the typical shape of a random network from a fixed class has been one of the major research focuses in phylogenetics over the last couple of years. In this extended abstract, we consider two subclasses of the (recently introduced) class of semi-simplex phylogenetic networks, namely, semi-simplex tree-child networks and semi-simplex galled trees. We clarify their sizes relative to the (known) sizes of general tree-child networks and galled trees, respectively, and prove limit laws for parameters of random networks from these classes. Additional classes of semi-simplex networks will be considered in the journal version of this paper.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to d-combining tree-child networks where every reticulation node has now d ≥ 2 parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.

In the early 2000s, several phase change results from distributional convergence to distributional non-convergence have been obtained for shape parameters of random discrete structures. Recently, for those random structures which admit a natural martingale process, these results have been considerably improved by obtaining refined asymptotics for the limit behavior. In this work, we propose a new approach which is also applicable to random discrete structures which do not admit a natural martingale process. As an example, we obtain refined asymptotics for the number of leaves in random point quadtrees. More applications, for example to shape parameters in generalized m-ary search trees and random gridtrees, will be discussed in the journal version of this extended abstract.

The Wiener index has been studied for simply generated random trees, nonplane unlabeled random trees, and a huge subclass of random grid trees containing random binary search trees, random median-of-(2k+1) search trees, random $m$-ary search trees, random quadtrees, random simplex trees, etc. An important class of random grid trees for which the Wiener index was not studied so far is random digital trees. In this work, we close this gap. More precisely, we derive asymptotic expansions of moments of the Wiener index and show that a central limit law for the Wiener index holds. These results are obtained for digital search trees and bucket versions as well as tries and PATRICIA tries. Our findings answer in the affirmative two questions posed by Neininger.

We show that a wide class of linear cost measures (such as the number of leaves) in random d -dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, …, 8, then the limit law is normal; if d ≥ 9 then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering m -ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.