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

Abstract

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.