FAQ
© 2018 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-90921
URL: http://ediss.sub.uni-hamburg.de/volltexte/2018/9092/


Resilience and anti-Ramsey properties of sparse random graphs and dense hypergraphs

Ausfallsicherheit und Anti-Ramsey-Eigenschaften von dünnen Zufallsgraphen und dichten Hypergraphen

Schnitzer, Jakob

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


Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Schacht, Mathias (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 22.03.2018
Erstellungsjahr: 2017
Publikationsdatum: 12.04.2018
Kurzfassung auf Englisch: 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.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende