Wider research context/theoretical framework

This proposal aims at shedding light on the large-scale behavior of random discrete structures, such as trees and tree-like structures. Such objects appear in numerous scientific fields, ranging from automata theory in computer science to phylogenetic trees in biology. In each case one is interested in understanding the typical shape of such objects, however the precise questions studied can be as diverse as the objects themselves. There are many conjectures about the behavior of these objects, which are in many cases widely open. Often not even the basic counting problem has been solved. In some cases the difficulties arise due to the still mysterious phenomenon of stretched exponentials m^(n^s), where m>0 and 0<s<1.

Research questions/objectives

The aim of the proposed projects is to gain new insights into the presence of stretched exponentials in asymptotic enumeration. We plan to address the following subjects:

• developing a generic method to prove Theta-results involving stretched exponentials
• determining the multiplicative constant and the D-finite behavior
• analyzing the shape characteristics of directed acyclic graphs and related structures

Approach/methods

At the core lies the detailed analysis of a class of two-parameter recurrence relations with special weights. This class is motivated by a weighted model of lattice paths that is bijectively connected to the tree-like structures we will analyze using, e.g., the symbolic method and generating functions. The further analysis then requires the usage of computer algebra in order to numerically and heuristically conjecture and prove the asymptotics. Hereby, we need to analyze ordinary differential equations and work with Newton polygons. Furthermore, we will refine the analysis to derive expressions for the involved constants using, e.g., the saddle point method and singularity analysis.

Level of originality/innovation

The biggest innovation is a new generic method to prove stretched exponentials and analyze the respective counting sequences. So far the saddle point method is the only generic method for proving such a phenomenon. This is the gap that this research proposal will close: We will develop a new versatile method to prove stretched exponentials and show that this phenomenon is not as rare as could be expected also proving many open conjectures. Our approach enables a detailed analysis of these objects and gives access to their limit shape characteristics.

Primary researchers involved

The team consists of Michael Wallner (PI) and a PhD student (to be recruited) who will work at the Institute of Discrete Mathematics at the TU Wien. During the project we plan to closely interact with Michael Fuchs and Hsien-Kuei Hwang from Taiwan, and Anthony Guttmann from Australia. Further collaborations are planned with Andrew Elvey Price, Wenjie Fang, Bernhard Gittenberger, Michael Drmota, and others.