| Autor(en): |
Mihyun Kang |
Titel: |
Random planar structures and random graph processes |
| Gutachter: |
Günter M. Ziegler; Hans Jürgen Prömel; Michal Karonski |
| Erscheinungsdatum: |
27.07.2007 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-10079034)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
planare Graphen, zufällige Graphen, rekursive Methode, Singularitätenanalyse, probabilistische Methoden |
| Schlagwörter (eng): |
planar graphs, random graphs, recursive method, singularity analysis, probabilistic methods |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Zitationshinweis: |
Kang, Mihyun:
Random planar structures and random graph processes;
Habilitationsschrift,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 27.07.2007, urn:nbn:de:kobv:11-10079034
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| Diese Habilitationsschrift richtete auf zwei diskrete Strukturen aus: planare Strukturen und zufällige Graphen-Prozesse.
Zunächst werden zufällige planare Strukturen untersucht, mit folgende Gesichtspunkte:
- Wieviele planare Strukturen gibt es?
- Wie kann effizient eine zufällige planare Struktur gleichverteilt erzeugt werden?
- Welche asymptotischen Eigenschaften hat eine zufällige planare Struktur mit hoher Wahrscheinlichkeit?
Um diese Fragen zu beantworten, werden die planaren Strukturen in Teile mit höherer Konnektivität zerlegt. Für die asymptotische Enumeration wird zuerst die Zerlegung als das Gleichungssystem der generierenden Funktionen interpretiert. Auf dem Gleichungssystem wird dann Singularitätenanalyse angewendet. Für die exakte Enumeration und zufällige Erzeugung wird die rekursive Methode verwendet. Für die typischen Eigenschaften wird die probabilistische Methode auf asymptotischer Anzahl angewendet.
Des Weiteren werden zufällige Graphen-Prozesse untersucht. Zufällige Graphen wurden zuerst von Erdos und Renyi eingeführt und untersucht weitgehend seitdem. Ein zufälliger Graphen-Prozess ist eine Markov-Kette, deren Zustandsraum eine Menge der Graphen mit einer gegebenen Knotenmenge ist. Der Prozess fängt mit isolierten Konten an, und in jedem Ablaufschritt entsteht ein neuer Graph aus dem aktuellen Graphen durch das Hinzufügen einer neuen Kante entsprechend einer vorgeschriebenen Regel. Typische Fragen sind:
- Wie ändert sich die Wahrscheinlichkeit, dass ein von einem zufälligen Graphen-Prozess erzeugter Graph zusammenhängend ist?
- Wann erfolgt der Phasenübergang?
- Wie groß ist die größte Komponente?
In dieser Habilitationsschrift werden diese Fragen über zufällige Graphen-Prozesse mit Gradbeschränkungen beantwortet. Dafür werden probabilistische Methoden, insbesondere Differentialgleichungsmethode, Verzweigungsprozesse, Singularitätsanalyse und Fourier-Transformationen, angewendet.
|
| Abstract (eng): |
| This thesis focuses on two kinds of discrete structures: planar structures, such as planar graphs and subclasses of them, and random graphs, particularly graphs generated by random processes.
We study first planar structures from the following aspects.
- How many of them are there (exactly or asymptotically)?
- How can we efficiently sample a random instance uniformly at random?
- What properties does a random planar structure have, with high probability?
To answer these questions we decompose the planar structures along the connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating functions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the recursive method. For typical properties of random planar structures we use the probabilistic method, together with the asymptotic numbers.
Next we study random graph processes. Random graphs were first introduced by Erdos and Renyi and studied extensively since. A random graph process is a Markov chain whose stages are graphs on a given vertex set. It starts with an empty graph, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. Recently random graph processes with degree restrictions received much attention. In the thesis, we study random graph processes where the minimum degree grows quite quickly with the following questions in mind:
- How does the connectedness of a graph generated by a random graph process change as the number of edges increases?
- When does the phase transition occur?
- How big is the largest component?
To investigate the random graph processes we use the probabilistic method, Wormald''s differential equation method, multi-type branching processes, and the singularity analysis. |
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
  | | | | | | | | | | | | | | | | | | | | | | | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Jan
12 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Feb
13 | Mar
13 | Apr
13 | May
13 |
| Monat | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Jan
12 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Jan
13 | Feb
13 | Mar
13 | Apr
13 | May
13 | | Startseite | 3 | 2 | 1 | 2 | 2 | 1 | | 4 | 2 | 1 | 3 | 3 | 2 | 1 | 1 | 3 | 5 | 1 | 2 | 6 | | 1 | | PDF | 5 | 10 | 2 | 6 | 4 | 6 | 2 | 7 | 1 | 2 | 10 | 8 | 10 | 5 | 9 | 8 | 4 | 16 | 14 | 22 | 18 | 27 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 46 (2 pro Monat)
- PDF – 196 (8.52 pro Monat)
|
