Singularity analysis of discrete differential equations with one catalytic variable and applications

Abstract

In der enumerativen Kombinatorik werden diskrete Strukturen, welche rekursivin kleinere Instanzen zerlegt werden können, oft durch eine funktionalgleichung beschrieben. Die Lösung einer solchen Funktionalgleichung ist die sogenannte generierende Funktion der jeweiligen Struktur. Genauer gesagt, ist sie eine formale Potenzreihe mit Koeffizienten an, die der Anzahl der Instanzen der Größe n der Struktur entspricht. Bender war der erste der bewies, dass Lösungen von Funktionalgleichungen mit nicht-negativen Koeffizienten analytische Funktionen mit nicht-negativen Taylor-Koeffizienten sind und an ihrem Konvergenzradius reine Wurzelsingularität haben. Als Konsequenz erfüllen ihre Koeffizienten die asymptotische Abschätzung c n^(−3/2)r^(−n) wenn n gegen unendlich strebt, wobei c eine berechenbare Konstante ist. Diese Beobachtung wurde auf Systeme von Funktionalgleichungen von Drmota, Lalley und Woods und kürzlich auch auf diskrete Differentialgleichungen erster Ordnung in einer katalytischen Variablen erweitert.In dieser Dissertation untersuchen wir das singuläre Verhalten von Lösungendiskreter Differentialgleichungen höherer Ordnung und wenden unsere Techniken und Ergebnisse auf ein offenes Problem hinsichtlich Mustererscheinungen in zufälligen planaren Karten an.

It is a classic technique in enumerative combinatorics to describe discrete structures by a functional equation if they satisfy a recursive decomposition. Its solution is a formal power series with coefficients an that equal the number of instances of size n. Bender was the first to prove that solutions to functional equations with non negative coefficients are analytic functions with non-negative Taylor coefficients that have a square root singularity at their radius of convergence r. As a consequence, their coefficients satisfy the asymptotic estimate c n^(−3/2)r^(−n), for a computable constant c as n tends to infinity. This observation was extended to systems of functional equations by Drmota, Lalley and Woods and recently, to first order discrete differential equation in one catalytic variable by Drmota, Noy and Yu. In this thesis we study the singular behaviour of solutions to higher order discrete differential equations and apply our techniques and results to an open problem concerning pattern occurrences in random rooted planar maps.