Volltextdatei(en) vorhanden
Titel: Resilience and anti-Ramsey properties of sparse random graphs and dense hypergraphs
Sonstige Titel: Ausfallsicherheit und Anti-Ramsey-Eigenschaften von dünnen Zufallsgraphen und dichten Hypergraphen
Sprache: Englisch
Autor*in: Schnitzer, Jakob
Erscheinungsdatum: 2017
Tag der mündlichen Prüfung: 2018-03-22
Zusammenfassung: 
This thesis contains three theorems in graph theory and their proofs. The first
result is a optimal (k-2)-degree condition for the existence of Hamiltonian cycles
in hypergraphs. We describe a well-known extremal example X_{k,l} for k >= 3
and l < k/2, a k-uniform hypergraph which contains no Hamiltonian l-cycle, and
prove that any sufficiently large hypergraph H with δ_{k-2}(H) > δ_{k-2}(X_{k,l}) contains a Hamiltonian l-cycle.

The second result is a transference of the bandwidth theorem to sparse random graphs.
For p > C (log n/n)^(1/Δ), we show that asymptotically almost surely for any
subgraph G of G(n,p) with a minimum degree of at least ((k-1)/k + o(n))pn
each vertex neighbourhood contains many copies of K_s the following
holds: Let H be a graph on n vertices with maximum degree at most ∆, bandwidth at most βn and suppose that there is a proper k-colouring of H and at least Ω(p^(-2)) vertices in H whose neighbourhood contains only s colours. Then G contains H.

The third result gives the thresholds for G(n,p) to have the rainbow Ramsey
property for cliques. An upper bound on the threshold for general graphs was
proved before and for cliques on at least 19 vertices the matching lower bound was
also known. We prove a matching lower bound on the threshold for all cliques on
at least 5 vertices and prove matching lower and upper bounds for K_4.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/7650
URN: urn:nbn:de:gbv:18-90921
Dokumenttyp: Dissertation
Betreuer*in: Schacht, Mathias (Prof. Dr.)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat  
Dissertation.pdf689.32 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

34
Letzte Woche
Letzten Monat
geprüft am 13.04.2021

Download(s)

13
Letzte Woche
Letzten Monat
geprüft am 13.04.2021
Werkzeuge

Google ScholarTM

Prüfe