Computer-assisted analytic methods for discrete problems

Abstract

The subject of this thesis is the application of computer algebra systems, MAPLE in particular, to asymptotic problems coming from discrete mathematics. Two specific problems are examined.<br />The first is concerned with patterns in labeled trees. We count the average number of times a particular pattern matches a tree of size n. Assuming that every tree of size n is equally likely, it is shown that the limiting distribution of the number of occurrences of the pattern is asymptotically normal, with mean value ~[mu]*n and variance ~[sigma]2 [[sigma] hoch 2]*n with computable constants [mu]>0 and [sigma]>=0. We provide an algorithm to compute [mu] explicitly and a MAPLE program that does most of the work. This part of the thesis is based on the paper ``The Distribution of Patterns in Random Trees'' coauthored with Frédéric Chyzak and Michael Drmota.<br />In the second part of the thesis, we generalize a class of functions which were introduced by Hayman and which we thus call Hayman-admissible. Hayman proved that the suitably normalized coefficients of these functions asymptotically follow a Gaussian distribution. He also assembled a useful list of closure properties, i.e., operations on Hayman-admissible functions that generate other Hayman-admissible functions. We generalize Hayman's result to functions in two dimensions, conserving many closure properties. We also present a MAPLE program that tests if a given function belongs to this class. This part of the thesis is based on the paper ``Extended Admissible Functions and Gaussian Limiting Distributions'' coauthored with Michael Drmota and Bernhard Gittenberger.<br />

Diese Doktorarbeit beschäftigt sich mit mathematischen Methoden zur asymptotischen Behandlung von diskreten mathematischen Problemen mit Computer-Unterstützung. Konkret werden dabei zwei verschiedene Probleme behandelt.<br />Im ersten Teil der Arbeit werden Muster in (markierten) Bäumen untersucht. Ein Muster ist ein bestimmter vorgegebener Baum. Wir nehmen alle Bäume einer bestimmten Größe n als gleich wahrscheinlich an und untersuchen, wie oft das vorgegebene Muster im Durchschnitt vorkommt. Wir zeigen, dass die Anzahl der Muster einen zentralen Grenzwertsatz erfüllt. Im Speziellen kann für jedes Muster auch durch Lösung eines zugehörigen polynomiellen Gleichungssystems der Erwartungswert explizit berechnet werden. Ein MAPLE-Programm, das den größten Teil dieser Berechnungen erledigt, ist Teil der Arbeit. Wir besprechen weiters einige Möglichkeiten der Verallgemeinerung auf andere Muster oder andere Graphen. Dieser Teil der Dissertation basiert auf der gemeinsamen Arbeit ``The Distribution of Patterns in Random Trees'' mit Frédéric Chyzak und Michael Drmota.<br />Im zweiten Teil der Arbeit beschäftigen wir uns mit dem Begriff der ``zulässigen'' Funktionen, den Hayman 1956 eingeführt hat. Er bewies, dass geeignet normalisierte Koeffizienten von zulässigen Funktionen asymptotisch einer Normalverteilung folgen. Hayman präsentierte auch eine Liste von Basisfunktionen und Abschlussbedingungen, unter denen aus zulässigen Funktionen andere zulässige Funktionen erzeugt werden können. Wir verallgemeinern Haymans Ergebnis auf Funktionen in zwei Variablen, um damit einen weiteren Parameter untersuchen zu können, und präsentieren ein MAPLE-Programm, das für eine beliebige gegebene Funktion automatisch testet, ob sie zulässig (``extended admissible'') ist. Dieser Teil der Dissertation basiert auf der gemeinsamen Arbeit ``Extended Admissible Functions and Gaussian Limiting Distributions'' mit Michael Drmota und Bernhard Gittenberger.