Local density properties of Andrásfai graphs and powers of Hamiltonian cycles in hypergraphs

Abstract

We present three results concerning different aspects of extremal and probabilistic combinatorics and their proofs. In the first part we study the local density conditions of graphs homomorphic to a generalised Andrásfai graph. The second part of this thesis is dedicated to a Hamiltonian cycle problem in 3-uniform hypergraphs. We study which minimum pair-degree condition suffices to ensure the existence of a squared Hamiltonian cycle in a 3-uniform hypergraph. This is motivated by Pósa’s conjecture which asked for a minimum degree condition that implies the existence of a second power of a Hamiltonian cycle in a graph. In the third part we continue the study of Hamiltonian cycle problems, but this time in randomly perturbed k-uniform hypergraphs.

Wir stellen drei Resultate, die verschiedene Aspekte der extremalen und probabilistischen Kombinatorik betreffen, und deren Beweise vor. Im ersten Teil untersuchen wir lokale Dichtebedingungen von Graphen, die homomorph zu einem generalisierten Andrásfai-Graphen sind. Der zweite Teil dieser Arbeit widmet sich Hamiltonkreisproblemen in 3-uniformen Hypergraphen. Wir untersuchen, welche minimale Paargradbedingung ausreichend ist, um die Existenz eines Quadrathamiltonkreises in 3-uniformen Hypergraphen zu gewährleisten. Dies ist motiviert durch Pósa’s Vermutung, welche nach einer Minimalgradbedingungen fragt, die die Existenz eines Quadrathamiltonkreises in Graphen sicherstellt. Im dritten Teil werden ebenfalls Hamiltonkreisprobleme untersucht. Dieses Mal jedoch in zufällig perturbierten k-uniformen Hypergraphen.