FAQ
© 2017 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-85785
URL: http://ediss.sub.uni-hamburg.de/volltexte/2017/8578/


Threshold Results for Cycles

Schwellenwertergebnisse für Kreise

Schulenburg, Fabian

pdf-Format:
 Dokument 1.pdf (996 KB) 


Freie Schlagwörter (Deutsch): Scharfe Schwellenwerte , Hamiltonkreise , Satz von Ramsey , Schurgleichung
Freie Schlagwörter (Englisch): sharp thresholds , Hamiltonian cycles , Ramsey´s Theorem , Schur equation
Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Schacht, Mathias (Prof. PhD)
Sprache: Englisch
Tag der mündlichen Prüfung: 23.06.2017
Erstellungsjahr: 2016
Publikationsdatum: 04.07.2017
Kurzfassung auf Deutsch: In dieser Arbeit werden zwei Probleme der extremalen Kombinatorik untersucht. Eine typische Fragestellung der letzten Jahre in diesem Forschungsbereich beschäftigt sich mit der Übertragung klassischer Resultate auf dünne zufällige Strukturen. In dieses Themengebiet fällt auch der erste Teil dieser Arbeit, in der Ramsey-Eigenschaften von zufälligen Teilmengen diskreter Strukturen analysiert werden. Für zwei Graphen F und G schreibe dabei G->F_r, wenn für jede Kantenfärbung von G mit r Farben eine einfarbige Kopie von F existiert. Im Jahr 1995 haben Rödl und Rucinski für den binomialen Zufallsgraphen G(n,p) sowie alle Graphen F und jede Anzahl an Farben r den Schwellenwert p=p(F,r) der Eigenschaft G(n,p)->F_r bestimmt. Friedgut et al. erweiterten dies 2006 für den Fall eines Dreiecks F und r=2, indem sie zeigten, dass der Schwellenwert dann scharf ist. In dieser Arbeit wird Friedgut’s Ergebnis auf eine größere Klasse von Graphen inklusive aller Kreise F erweitert. Auf eine ähnliche Weise wird zudem gezeigt, dass die Eigenschaft, dass eine zufällige Teilmenge der ganzen Zahlen in jeder 2-Färbung ein einfarbiges Schur Tripel enthält, einen scharfen Schwellenwert hat.

Der zweite Teil der Arbeit beschäftigt sich mit Hamiltonkreisen in Hypergraphen. 1952 hat Dirac gezeigt, dass jeder Graph auf n>2 Ecken mit Minimalgrad mindestens n/2 einen Hamiltonkreis enthält. Die Übertragung von Dirac’s Theorem auf Hypergraphen führt zu verschiedenen Fragestellungen, da es für Kreise und Minimalgrad unterschiedliche Konzepte in Hypergraphen gibt. Über die letzten 20 Jahre haben unterschiedliche Forscher Ergebnisse zu diesem Themenkomplex beigetragen. In dieser Arbeit wird diese Forschung fortgesetzt und eine approximative Version des Falles von sogenannten dünnen l-Kreisen und einer (k-2)-Minimalgradbedingung in k-uniformen Hypergraphen vorgestellt.
Kurzfassung auf Englisch: In this thesis we investigate two problems in extremal and probabilistic combinatorics. In the first part we analyse sharp thresholds for Ramsey-type properties of random discrete structures, which contributes to the common theme in recent years to transfer classical results to sparse random structures. For two graphs F and G let G->F_r denote that for every edge colouring of G with r colours there exists a monochromatic copy of F. In 1995 Rödl and Rucinski determined the threshold p=p(F,r) for G(n,p)->F_r for the binomial random graph G(n,p) and any F and r. Furthermore, in 2006 Friedgut et al. proved that in the case that r=2 and F being a triangle the threshold is sharp. In the first part we generalise Friedgut’s result to a larger class of graphs F including all cycles. Related to this question we also show that the property that a random subset of the integers contains in every 2-colouring a monochromatic Schur triple has a sharp threshold.

In the second part we present a result concerning Hamiltonian cycles in hypergraphs. In 1952 Dirac showed that every graph on n>2 vertices with minimum degree at least n/2 contains a Hamiltonian cycle. Transferring Dirac’s Theorem to hypergraphs leads to multiple open questions since there are several notions of cycles and of minimum degree in k-uniform hypergraphs for k>2. Over the last 20 years various researchers proved such extensions to hypergraphs. In this thesis we continue this line of research and obtain an approximate version for so-called loose l-cycles and a (k-2)-minimumdegree condition in k-uniform hypergraphs.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende