Volltextdatei(en) vorhanden
Titel: Threshold Results for Cycles
Sonstige Titel: Schwellenwertergebnisse für Kreise
Sprache: Englisch
Autor*in: Schulenburg, Fabian
Schlagwörter: Scharfe Schwellenwerte; Hamiltonkreise; Satz von Ramsey; Schurgleichung; sharp thresholds; Hamiltonian cycles; Ramsey´s Theorem; Schur equation
Erscheinungsdatum: 2016
Tag der mündlichen Prüfung: 2017-06-23
Zusammenfassung: 
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.

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.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/7252
URN: urn:nbn:de:gbv:18-85785
Dokumenttyp: Dissertation
Betreuer*in: Schacht, Mathias (Prof. PhD)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung Prüfsumme GrößeFormat  
Dissertation.pdfad447c51bf45cb2c7391d44fa834cc04995.66 kBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Diese Publikation steht in elektronischer Form im Internet bereit und kann gelesen werden. Über den freien Zugang hinaus wurden durch die Urheberin / den Urheber keine weiteren Rechte eingeräumt. Nutzungshandlungen (wie zum Beispiel der Download, das Bearbeiten, das Weiterverbreiten) sind daher nur im Rahmen der gesetzlichen Erlaubnisse des Urheberrechtsgesetzes (UrhG) erlaubt. Dies gilt für die Publikation sowie für ihre einzelnen Bestandteile, soweit nichts Anderes ausgewiesen ist.

Info

Seitenansichten

157
Letzte Woche
Letzten Monat
geprüft am 27.03.2024

Download(s)

49
Letzte Woche
Letzten Monat
geprüft am 27.03.2024
Werkzeuge

Google ScholarTM

Prüfe