F50-03: Combinatorics of Tree-Like Structures and Enriched Trees
This project part has four major lines of research: first, the study of the asymptotic behavior of the complexity of Boolean functions which are represented by trees and randomly generated according to a given probability model for a class of trees. Second, the study of random enriched trees. These are belong to a particular class of directed acyclic graphs. The concept is a slight generalization of that of trees and is closely to predicate logic. The conceptually simplest example is in bijection to the set of lambda terms used in lambda-calculus. The third line is the comparison of so-called simply generated trees and other classes of rooted trees which are in some sense almost simply generated trees. The most prominent example that of Polya trees, but there are also other such tree classes like those which are related to planar maps. The fourth topic is the study of shape parameters of random lattice paths. One important class, so-called Lukasiewicz paths, is in bijection to simply generated trees.
The main methods to be used are based on analytic combinatorics (generating functions for combinatorial structures) in conjunction with singularity analysis for implicitly defined functions and the kernel method.