edoc-Server der Humboldt-Universität zu Berlin

Dissertation

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.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

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.
Startseite: 3 Zugriffe PDF: 4 Zugriffe PDF: 2 Zugriffe Startseite: 5 Zugriffe PDF: 2 Zugriffe Startseite: 1 Zugriffe Startseite: 2 Zugriffe PDF: 8 Zugriffe PDF: 3 Zugriffe PDF: 3 Zugriffe PDF: 6 Zugriffe PDF: 2 Zugriffe Startseite: 1 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe PDF: 1 Zugriffe PDF: 3 Zugriffe PDF: 6 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 11 Zugriffe Startseite: 3 Zugriffe PDF: 20 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 7 Zugriffe PDF: 11 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 9 Zugriffe Startseite: 1 Zugriffe PDF: 10 Zugriffe PDF: 8 Zugriffe Startseite: 4 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 8 Zugriffe PDF: 13 Zugriffe PDF: 15 Zugriffe PDF: 9 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe PDF: 16 Zugriffe
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
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Monat 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
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Startseite 3   5 1 2         1 2         2 3   1     2 1   4 2 2       2 2  
PDF 4 2 2   8 3 3 6 2 3 6 1 3 6 3 11 20 6 7 11 7 9 10 8 7 3 8 13 15 9 14 14 16

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 35 (1.03 pro Monat)
  • PDF – 240 (7.06 pro Monat)
 
 
Generiert am 26.07.2014, 06:40:35