Functional equations for lattice paths and tree structures

This project is dedicated to the study of two fundamental combinatorial structures: lattice paths and tree-like structures. Such objects are not restricted to mathematics. Trees are used in computer science as data structures and as models for algorithms. Lattice paths appear in chemistry as models for polymers, or in queuing theory as models for birth-death processes. These models are described by an (infinite) family of objects associated with a size function. The most natural choice are the number of steps for lattice paths and the number of nodes for trees. Then, one is first of all interested in determining the number of objects of a given size. The most important concept for this purpose are generating functions. These are (formal) power series whose coefficients are given by these numbers. They translate these models into functional equations on the respective generating functions. These equations are either of the algebraic type or linear differential equations with polynomial coefficients. Their analysis is the key to the understanding of the respective models. With the concepts of "analytic combinatorics" one interprets these generating functions as expansions of functions defined on complex numbers. Then, one can use techniques from complex analysis, and sophisticated methods like the kernel method and the theory of holonomic functions. We plan to study three subprojects. As stated above, we are always interested in the (asymptotic) number of certain objects. First, we study lattice paths confined to stay below a line of irrational slope. These paths start at the origin, and we allow to jump a unit step north or east, but may never jump across a line of irrational slope. The case of integer and rational slope is a classical topic in combinatorics and probability theory. Second, we consider lattice paths with catastrophes in higher dimensions. In dimension two these paths also start in the origin and are confined to stay in the first quadrant. We also fix a set of steps, say north, east, south, and west, but we also allow additional steps, the so-called catastrophes. These are jumps from any distance to one of the axes. Next to their (asymptotic) number we are also interested in additional parameters, like the average number of catastrophes. Such paths can be interpreted as models for queues which allow a reset, like a crash of a computer program. Third, we study compacted trees. These are trees, in which redundant information in form of repeatedly appearing subtrees has been deleted and replaced by pointers. Such structures are used in the design of compilers and allow efficient and compact code, as well as in the compression of data.

Mathematical models are ubiquitous in science. Among other things, they allow the analysis of algorithms in computer science, the study of polymers in chemistry, or the description of evolutionary relationships in biology. This project dealt with two classes of such fundamental models: lattice paths and tree structures. The simplest examples for lattice paths are paths that travel north, east, south, or west from the origin with jumps of length one; for tree structures the simplest examples are binary or phylogenetic trees. Our main results extend these two classes by new models that exhibit naturally occurring but difficult-to-model phenomena. In general, my research belongs to enumerative and analytic combinatorics, which is driven by the fundamental questions "How many are there?" and "What is typical?". In terms of the models above, we answered the questions of how many lattice paths with a certain number of steps and how many trees with a certain number of nodes there are, and based on that, what a typical representative looks like. In the area of lattice paths, we dealt with paths in non-convex domains, which have recently become more popular, but about which very little was known. We were able to solve the counting problem of king steps (like a king in chess) and show that there is a deep connection to the same problem in convex domains. This allowed us to show that the underlying generating function satisfies a linear differential equation with polynomial coefficients, but not an algebraic equation, which in turn allows the quick and efficient generation of such paths. In the area of tree structures, we investigated compacted trees that appear naturally in compression methods in computer science. In these trees, repeatedly occurring subtrees are deleted and replaced by pointers to save memory. In the asymptotic counting problem, we were able to prove a previously very rarely observed phenomenon: the appearance of stretched exponentials. For trees with n nodes, these are terms of the form a^(n^s) with real constants a and s. We were able to develop a new method that proves such terms and only requires information about the underlying recurrence relation. Furthermore, we were able to apply this method to the open problem of counting minimal deterministic automata with a binary alphabet and also prove a stretched exponential. All this makes us optimistic that this method will solve many open counting problems in the future.