Existence and enumeration of spanning structures in sparse graphs and hypergraphs

Abstract

Diese Dissertation beschäftigt sich mit der Robustheit von dünnen Graphen und Hypergraphen bezüglich des Auftretens gegebener aufspannender Subgraphen. Insbesondere werden Analoga des Bandweitentheorems für zufällige und pseudozufällige Graphen und ein sogenanntes Dirac-artiges Theorem für Berge-Hamiltonkreise in zufälligen r-uniformen Hypergraphen bewiesen. Zudem werden Bedingungen, die die Existenz von Regenbogenmatchings in kantengefärbten Multigraphen sichern, bestimmt und die Anzahl der Spannbäume in Graphen, die zufällig aus Unterfamilien von serien-parallelen Graphen gewählt werden, studiert.

This thesis examines the robustness of sparse graphs and hypergraphs with respect to containing copies of given spanning subgraphs. In particular, we prove analogues of the bandwidth theorem for random and pseudorandom graphs, as well as a Dirac-type theorem for Hamilton Berge cycles in random r-uniform hypergraphs. Furthermore, we determine conditions for the existence of rainbow matchings in edge-coloured multigraphs and study the number of spanning trees in graphs chosen uniformly at random from subfamilies of series-parallel graphs.