Random Recursive Structures of Small Diameters

The major aims of the Austrian-Taiwanese joint project are: (1) to get a deeper understanding of the stochastic nature of random trees and more general structures which have a small diameter, (2) development and advancement of general analytic tools, (3) stimulating interdisciplinary research on an international level. Tree structures play an important role in many areas like computer science, quantum mechanics, biology and many more, and also in many subfields inside mathematics. They serve for instance as data structure. If one faces random data and stores them in a tree, then the resulting tree will be a random tree. In order to understand how this tree typically looks like (for instance for designing efficient algorithms for information retrieval which exploit the knowledge on the shape of the tree), it is necessary to consider large random trees and analyze them systematically. Trees may serve as a model of some real world phenomenon which we want to understand. In order to analyze a model, one starts with simple models, like e.g. branching processes. This model is very well understood, but its drawback is that there are many situations where it is not realistic. There are other models like binary search trees which are well-suited for certain frameworks in computer science. Many of those new models have the property that the so-called diameter is small in comparison to the old models. In contrary to the branching process models, there exists no general framework for the new models, but only many partial results for many different models of trees with small diameter, Partial results indicate that such a framework can be described by means of Riccati-like differential equations. Our aim is to explore this phenomenon and to enhance existing methods for retrieving the desired information from these equations. A further goal of the project is to deepen the understanding of the typical shape of various classes of random trees. This is done by first studying the profile of random trees and then several shape parameters simultaneously. In applications one is often interested in the number of way to decompose a complex structure in distinct parts. This is a highly nontrivial problem, but we hope that the tools we develop during the project will enable us to obtain deep results on this question. In this context, there are examples of tree models from biology, but also other interesting structures from other fields of mathematics. Finally, a particular problem from information theory shall be investigated: If we do not focus on the tree size but on some other parameter, then this gives rise to a bias towards small diameter and probably trees with very different behaviour.

Tree-like structures (think of an ancestor tree or Darwin's tree of life) are fundamental mathematical objects. With the advent of computer science, trees serve as data structures and many new tree models were invented. Similarly, Darwin's tree of life is not the state of the art when considering bacterial evolution. So, many new models are considered to understand evolution in various contexts. Those models are often not tree-like but rather network-like. A further structure that has been studied is random graphs. It is simple but still structurally rich, but it has large diameter, as opposed to many real-world networks. Thus, recently many new graph models popped up in order to understand how such networks evolve and what are their driving forces. One of those models is based on another structure called hypergraph. The project aimed at increasing the understanding (describe the typical shape) of random structures like those presented above. The way the project ran was manyfold: first, we picked a lot of structures from the literature, where certain structural parameters were unknown, in order to approach the open problems with our methods and fill the gaps. Second, we investigated the methodology itself and tried to increase its power. Structures dealt with were digital search trees, several classes of phylogenetic networks and a class of hypergraphs. An important parameter of digital search trees is their profile, a fine description of the silhouette you see when you scan the tree from the root to the top. Though studied for decades, fairly little was known, as the problem can only be described by very complicated equations. With the joint effort and a combination of a variety of methods we could extend the knowledge considerably and get complete knowledge of several related parameters, and likely the complete description of the profile in the near future. For hypergraphs, the important observations are the structural changes during the phase transition. Structure, order and size of the largest components could be completely described for a class of hypergraphs. The asymptotic and exact numbers of phylogenetic networks of given sizes were determined for some classes of such networks. This laid the ground for a further shape analysis, which has been done for basic parameters of some of these classes. On the methodological side, complete asymptotic expansions for what is known as Lagrangean forms were determined. Moreover, the saddle point method could be extended to generating functions appearing in the enumeration of Fishburn matrices. This is a breakthrough, as the method is conceptually simpler than the methods used so far, and in contrast to these specially taylored methods, it can be generalized to numerous problems of a similar nature and helped to prove several conjectures in the field.