| Autor(en): |
Deryk Simeon Osthus |
Titel: |
On the evolution of random discrete structures |
| Gutachter: |
Angelika Steger; Hans Jürgen Prömel; Joel H. Spencer |
| Erscheinungsdatum: |
26.04.2000 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-10013861)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
Zufällige Graphen, Graphentheorie, Wahrscheinlichkeitstheorie, Phasenübergang |
| Schlagwörter (eng): |
random graph, graph theory, probability, phase transition |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Zitationshinweis: |
Osthus, Deryk Simeon:
On the evolution of random discrete structures;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 26.04.2000, urn:nbn:de:kobv:11-10013861
|
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): |
| Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse
zufälliger diskreter Strukturen.
Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben.
Anfangs beginnt man mit einer sehr einfachen Struktur
(z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge
von ``Bausteinen''
(z.B. der Kantenmenge des vollständigen Graphen auf n Ecken).
Mit zunehmender Zeit werden zufällig
mehr und mehr Bausteine eingefügt.
Die grundlegende Frage, mit der sich diese Dissertation beschäftigt,
ist die folgende:
Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte
Struktur mit hoher Wahrscheinlichkeit aus?
Obwohl das Hauptthema der Dissertation die Evolution
zufälliger diskreter Strukturen ist, lassen sich die erzielten
Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen:
Zufällige Greedy-Algorithmen:
Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen
gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt.
Extremale Ergebnisse:
Es wird die Existenz von Graphen mit hoher Taillenweite und
hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert
werden.
Asymptotische Enumeration:
Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier
Graphen mit n Ecken und m Kanten bewiesen.
``Probabilistische'' Versionen klassischer S"atze:
Es wird eine probabilistische Version des Satzes von Sperner bewiesen. |
| Abstract (eng): |
| In this thesis, we study the evolution of random discrete structures.
Such evolution processes usually fit into the following general framework.
Initially (say at time 0), we start with a very simple structure
(e.g. a graph on n vertices with no edges) and a set of ``building blocks''
(e.g. the set of edges of the complete graph on n vertices).
As time increases, we randomly add more and more elements from our set
of building blocks.
The basic question which we shall investigate is the following:
what are the likely properties of the random structure produced by
the process at any given time?
Although this thesis is concerned with the evolution of random discrete
structures, the results obtained can also be summarized according to the
following keywords:
Random greedy algorithms:
we study the output of a random greedy algorithm which, for a given graph H,
produces a random H-free graph.
Extremal results:
improving on previous bounds, we prove the existence of graphs with high
girth and high chromatic number.
Asymptotic enumeration:
we prove sharp asymptotic bounds on the number of triangle-free graphs
with n vertices and m edges for a large range of m.
Probabilistic versions of ``classical'' theorems:
we prove a probabilistic version of Sperner's theorem on finite sets. |
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 | 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 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Feb
13 | Mar
13 | Apr
13 | May
13 | | Startseite | 2 | 3 | | 5 | 1 | 2 | | | | | 1 | 2 | | | | | 2 | 3 | | 1 | | | PDF | 4 | 4 | 2 | 2 | | 8 | 3 | 3 | 6 | 2 | 3 | 6 | 1 | 3 | 6 | 3 | 11 | 20 | 6 | 7 | 11 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 22 (1 pro Monat)
- PDF – 111 (5.05 pro Monat)
|
