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.