Open Access

Olaf Parczyk

• Embedding spanning structures into the random graph G(n,p) is a well-studied problem in random graph theory, but when one turns to the random r-uniform hypergraph H(r)(n,p) much less is known. In this thesis we will examine this topic from different perspectives, providing insights into various aspects of the theory of random graphs. Our results cover the determination of existence thresholds in two models, as well as an algorithmic approach. For the embeddings, we work with random and pseudorandom structures. Together with Person we first notice that a general result of Riordan can be adapted from random graphs to hypergraphs and provide sufficient conditions for when H(r)(n,p) contains a given spanning structure asymptotically almost surely. As applications, we discuss several spanning structures such as cubes, lattices, spheres, and Hamilton cycles in hypergraphs. Moreover, we study universality, i.e. when does an r-uniform hypergraph contain every hypergraph on n vertices with maximum vertex degree bounded by [delta]? For H(r)(n,p), it is shown with Person that this holds for p = w(ln n/n)1/[delta]) asymptotically almost surely by combining approaches taken by Dellamonica, Kohayakawa, Rödl, and Ruciński, of Ferber, Nenadov, and Peter, and of Kim and Lee. Any hypergraph that is universal for the family of bounded degree r-uniform hypergraphs has to contain [omega](nr-r/[delta]) edges. With Hetterich and Person we exploit constructions of Alon and Capalbo to obtain universal r-uniform hypergraphs with the optimal number of edges O(nr-r/[delta]) when r is even, r | [delta], or [delta] = 2. Furthermore, we generalise the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most m edges and no isolated vertices to hypergraphs. In an r-uniform hypergraph on n vertices a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. In collaboration with Allen, Koch, and Person we provide a first deterministic polynomial time algorithm, which finds asymptotically almost surely tight Hamilton cycles in random r-uniform hypergraphs with edge probability at least C log3 n/n. This result partially answers a question of Nenadov and Skorić and of Dudek and Frieze who proved that tight Hamilton cycles exist already for p = w(1/n) for r = 3 and p [größer/gleich] (e + o(1))/n for r [größer/gleich] 4 using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa, and Person and Nenadov and Skorić. Lastly, we study the model of randomly perturbed dense graphs introduced by Bohman, Frieze and Martin, that is, the union of any n-vertex graph G[alpha] with minimum degree at least [alpha]n and G(n,p). For any fixed [alpha] > 0, and p = w(n-2/([delta]+1)), we show with Böttcher, Montgomery, and Person that G[alpha] UG(n,p) almost surely contains any single spanning graph with maximum degree [delta], where [delta] [größer/gleich] 5. As in previous results concerning this model, the bound used for p is lower by a log-term in comparison to the conjectured threshold for the general appearance of such subgraphs in G(n,p) alone. The new techniques we introduce also give simpler proofs of related results in the literature on trees and factors.
• Das Finden von aufspannenden Strukturen im zufälligen Graphen G(n,p) is ein viel studiertes Problem in der Theorie der zufälligen Graphen, aber sobald man sich dem zufälligen r-uniformen Hypergraphen H(r)(n,p) zuwendet ist noch deutlich weniger bekannt. In dieser Arbeit beschäftigen wir uns mit diesem Thema aus verschiedenen Blickwinkeln und geben dabei einen Einblick in viele Aspekte des Studiums von zufälligen Graphen. Zu unseren Ergebnissen gehören sowohl die Bestimmung von Schwellenwerten in verschiedenen Modellen als auch ein algorithmischer Zugang. Für die Einbettungen arbeiten wir mit zufälligen und pseudozufälligen Strukturen. Zusammen mit Person stellen wir zuerst fest, dass sich ein allgemeines Ergebnis von Riordan von zufälligen Graphen auf Hypergraphen verallgemeinern lässt, und zeigen eine hinreichende Bedingung dafür, dass H(r)(n,p) eine gegebene aufspannende Struktur asymptotisch fast sicher enthält. Als Anwendung diskutieren wir verschiedene Strukturen, wie Würfel, Gitter und Hamiltonkreise in Hypergraphen. Desweiteren studieren wir Universalität, also die Frage, wann ein r-uniformer Hypergraph "alle" Hypergraphen auf n Knoten mit maximalem Knotengrad höchstens [delta] enthält. Für H(r)(n,p) zeigen wir mit Person, dass dies für p = w(ln n/n)1/[delta]) asymptotisch fast sicher stimmt, indem wir Ideen von Dellamonica, Kohayakawa, Rödl und Ruciński, von Ferber, Nenadov und Peter und von Kim und Lee kombinieren. Jeder Hypergraph, der universal für die Familie der gradbeschränkten Hypergraphen ist, muss mindestens [omega](nr-r/[delta]) Kanten besitzen. Mit Hetterich und Person nutzen wir Konstruktionen von Alon und Capalbo aus, um daraus universale r-uniforme Hypergraphen mit optimaler Kantenanzahl O(nr-r/[delta]) zu konstruieren, falls r gerade ist, r | [delta], or [delta] = 2. Darüberhinaus verallgemeinern wir ein Resultat von Alon und Asodi über optimale universale Graphen für die Familie der Graphen mit m Kanten und ohne isolierte Knoten auf Hypergraphen. In einem r-uniformen Hypergraphen auf n Knoten besteht ein enger Hamiltonkreis aus n Kanten, so dass es eine zyklsiche Anordnung der Knoten gibt, in der die Kanten zu aufeinanderfolgenden Segmenten gehören. In Kollaboration mit Allen, Koch und Person finden wir einen ersten deterministischen Polynomialzeitalgorithmus, der asymptotisch fast sicher einen engen Hamiltonkreis in H(r)(n,p) findet für p [größer/gleich] C log3 n/n. Damit beantworten wir teilweise eine Frage von Nenadov und Skorić und von Dudek und Frieze, die zeigten, dass enge Hamiltonkreise bereits für p [größer/gleich] (e + o(1))/n exisiteren für r [größer/gleich] 4 (p = w(1/n) for r = 3), indem sie die Methode des zweiten Moments anwendeten. Desweiteren verbessern wir zuvorige Algorithmen von Allen, Böttcher, Kohayakawa und Person und Nenadov und Skorić. Zuletzt widmen wir uns dem Modell der zufällig manipulierten dichten Graphen, dass von Bohman, Frieze und Martin eingeführt wurde. In diesem Modeel betrachten wir die Vereinigung von einem Graphen G[alpha] auf n Knoten mit Minimalgrad $[alpha]n and G(n,p). Für ein fixiertes [alpha] > 0, und p = w(n-2/([delta]+1)) zeigen wir mit Böttcher, Montgomery und Person, dass G[alpha] UG(n,p) asymptotisch fast sicher einen beliebigen aufspannenden Graphen auf n Knoten mit Maximalgrad [delta] ernhält, falls [delta] [größer/gleich] 5. Ebenso wie in vorherigen Ergebnissen in diesem Modell ist die Schranke an p um einen log-Faktor kleiner als der vermutete Schwellenwert für das Auftreten dieser Strukturen in G(n,p) alleine. Unsere neue Methode ergibt auch einfachere Beweise für einige verwandte Probleme über Bäume und Faktoren.