Stretched exponentials and beyond

Many mathematical problems begin with a simple question: "How many are there?" Its innocent and sometimes naive character hides the fact that its answer is often not only difficult but even impossible. Mathematically, this question belongs to enumerative combinatorics, but it appears in many different disciplines, ranging from computer science (e.g., analysis of algorithms) to biology (e.g., phylogenetic trees). Of primary interest are universal phenomena in large random structures. These describe the observation that many combinatorial structures are influenced by only a few global properties and do not depend on concrete details. This project is devoted to one such phenomenon: the occurrence of stretched exponentials in asymptotic counting. But what does this mean? A sequence of numbers is asymptotically equivalent to another if their common quotient tends towards 1. The idea here is that for a given complicated number sequence that is difficult to compute, a simpler representation is found that reflects its order of magnitude. In this way, approximations can be calculated efficiently and different number sequences can be compared with each other. For example, there are n!=n*(n-1)*...*2*1 many ways to arrange n different playing cards. An asymptotic formula is given here by Stirling`s formula, which shows that n! grows superexponentially. Asymptotic formulas can consist of different components that represent, for example, polynomial or exponential growth. Stretched exponentials are a component rarely observed so far, which roughly speaking lies between polynomial and exponential growth. They have the form a^(n^s) for real numbers a and s as well as a natural number n. Recently, some open problems have been solved in which the existence of stretched exponentials was ultimately responsible for their difficulty. The aim of this project is to develop generic methods to prove and compute such stretched exponentials. Furthermore, we want to classify a general class of two-parameter recurrence relations that have stretched exponentials. We then want to apply this result to open problems in mathematics, biology, physics or chemistry and hopefully find many new examples for the occurrence of stretched exponentials. Specifically, these are problems in automata theory, the compression of data structures, phylogenetics, algebraic group theory, queueing theory and many more. Our method is characterized by its interdisciplinarity and combines the fields of combinatorics, computer algebra, and complex analysis. Our results allow further in-depth analysis of additional parameters such as the typical running time of algorithms.

Discrete structures play a major role in many areas of our modern world. In this project, we studied networks ranging from computer science data networks to phylogenetic networks (models of evolutionary trees with recombination) in biology. Our main interest lay in their typical properties when they become extremely large. What does a typical representative look like? The word "typical" here refers to an object drawn uniformly at random from all objects of a given size. To answer this, we must first determine how many objects that size exist. While for small sizes one could in principle list all possibilities, this quickly becomes impossible as the size grows, and counting becomes highly nontrivial. Ideally, one would like a formula that is easy to calculate when it comes to counting something. In many cases, however, no such formula is known; often it does not exist at all, or it is too complicated. That is why we are interested in the best possible approximation as the size of the objects approaches infinity. This is referred to as an asymptotic formula. This asymptotic approach allows us to focus on the dominating structures and mask out rare ones. Let us take a network with n nodes. For instance, we may think of all graphs on n nodes and ask how many such graphs exist and what a typical one looks like. Then classic examples include polynomial growth such as n^2 or exponential growth such as 2^n. In some cases, however, these types are insufficient, as certain classes additionally include factors that grow faster than any polynomial but slower than any exponential. Such phenomena are referred to as "stretched exponentials" and take the form exp(c*n^s), where c is a constant and s a number between 0 and 1. Until recently, few instances exhibiting such a phenomenon were known. In our project, we were able to show that this phenomenon occurs in many discrete structures. Among other things, we were able to demonstrate it in an infinite number of classes of phylogenetic networks as well as in models of theoretical physics called Young tableaux with walls. With the help of these results, we were also able, for the first time, to successfully investigate the typical properties of these models. For example, we determined how frequently patterns such as the number of cherries occur in phylogenetic networks. We also identified new structural connections between different models via one-to-one mappings to weighted lattice path models. All of this now enables us to address the questions that formed the starting point for this work and to better understand the typical behavior of large discrete systems.