Titelaufnahme

Titel
Funktionale Grenzwertsätze in der Kombinatorik / Martin Zeiner
VerfasserZeiner, Martin
Begutachter / BegutachterinGittenberger, Bernhard
Erschienen2007
Umfang72 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2007
SpracheDeutsch
Bibl. ReferenzOeBB
DokumenttypDiplomarbeit
Schlagwörter (DE)Funktionale Grenzwertsätze / erzeugende Funktionen / Poissonapproximation / zufällige Strukturen / stochastische Prozesse / Kombinatorik / Sattelpunktmethode / Singularitätsanalyse
Schlagwörter (EN)functional limit theorems / generating functions / poisson process approximation / random structures / stochastic processes / combinatorics / saddle point method / singularity analysis
URNurn:nbn:at:at-ubtuw:1-16994 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Funktionale Grenzwertsätze in der Kombinatorik [1.48 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Wir betrachten kombinatorische Objekte der Größe n und zählen Unterstrukturen der Größe j (j=1..n). Für ein Objekt o sei X(j,o) diese Anzahl. Versehen wir die Menge der Objekte der Größe n mit einem Wahrscheinlichkeitsmaß, so werden die X(j,o) zu Zufallsvariablen X(j).

Für nichtganzzahlige j können wir beispielsweise linear interpolieren.

Skaliert man diesen Prozess noch geeignet, so kann man das Verhalten für n gegen unendlich untersuchen.

In dieser Arbeit studieren wir derartige Grenzwertsätze (sogenannte funktionale Grenzwertsätze), sowie Methoden, mit denen diese gezeigt werden können, und ihre Anwendungen in der Kombinatorik.

In Kapitel 1 geben wir die Definition stochastischer Prozesse und wichtige Eingenschaften an und stellen die behandelten Prozesse, insbesondere die Brown'sche Bewegung und davon abgeleitete Prozesse vor.

Da die betrachteten Prozesse ein Wahrscheinlichkeitsmaß auf den Räumen C[0,1], C[0,unendlich) oder D[0,1] induzieren, untersuchen wir die Konvergenz von Maßen speziell in diesen Räumen.

In Kapitel 2 werden Methoden vorgestellt, mit denen funktionale Grenzwertsätze gezeigt werden können: erzeugende Funktionen diskreter Zufallsvariablen und kombinatorischer Structuren, Sattelpunktmethode und Singularitätsanalyse zur Bestimmung der Koeffizienten und Poissonapproximation, um auftretende Abhängigkeiten zwischen Zufallsvariablen zu umgehen.

In Kapitel 3 zeigen wir, wo funktionale Grenzwertsätze in der Kombinatorik auftreten und wie diese mithilfe obiger Methoden bewiesen werden können. Zu den Beispielen zählen zufällige Bäume, Matrizen, Abbildungen, Permutationen, Mengenpartitionen und Urnenmodelle.

Zusammenfassung (Englisch)

Consider combinatorial objects of size n. Let X(j,o) the number of substructures of size j (j=1..n) of an object o. If we choose o randomly, then X(j,o) become random variables X(j). For non-integer we can define by linear interpolation a stochastic process. After suitable scaling we are able to study the behaviour of this process for n to infinity.

In chapter 1 we give an introduction to stochastic processes (especially we consider Gaussian processes, Brownian Motion, Brownian Bridge and Brownian Excursion) and study the convergence of probablitiy measures especially in C[0,1], C[0,infinity) and D[0,1].

In chapter 2 we present methodes which are useful to proof functional limit theorems in combinatorics: probability generating functions, generating functions of cmbinatorial structures, saddle point method and singularity analysis to determine their coefficients and poisson process approximation, which ca be used to avoid depedences of random variables which arise because of the combinatorial setup.

In chapter 3 we show how these methods can be used to proof functional limit theorems in combinatorics. Our examples are random trees, random matrices, random mappings, random permutations, random set partitions and urn models.