Homomorphism thresholds and embeddings of spanning subgraphs in dense graphs

Abstract

In this thesis we investigate structures in dense graphs. In the first part we analyse certain aspects of the interplay of minimum degree conditions and structural properties of large graphs with forbidden subgraphs, which is a central topic in extremal graph theory. More precisely, for a given family of graphs $F**$ we define the $chromatic threshold$ as the infimum over all $alpha in [0,1]$ such that every $n$-vertex $F**$-free graph $G$ with minimum degree at least $alpha n$ has a homomorphic image $H$ of bounded order, in other words, we insist that $G$ has bounded chromatic number. In 2013 the $chromatic threshold$ was determined by Allen et al. for all finite families of graphs.

Insisting that the homomorphic image $H$ of $G$ is $F**$-free as well, we get the definition of the $homomorphism threshold$, that is less well understood, and our first main theorem solves this question for the family of odd cycles up to a given length $2k-1$. Moreover in our secod main theorem we analyse the graph $H$ in more detail to get a deeper understanding for the structure of $G$.

In the second part we consider sufficient conditions for the existence of $k$-th powers of Hamiltonian cycles. Confirming a conjectures of Pósa from 1964 and Seymour from 1973, more then $20$ years ago Komlós, Sarközy, and Szemerédi obtained optimal minimum degree conditions for this problem by showing that every $n$-vertex graph with minimum degree at least $mu n$ for $mu = k / k+1$ contains the $k$-th power of a Hamiltonian cycle. For smaller values of $mu$ the given graph $G$ must satisfy additional assumptions, and in this direction Staden and Treglown showed in 2018 that $mu = 1/2 + epsilon$ is sufficient when we insist that every linear size induced subgraph has density $d > 0$. This bound on $mu$ is optimal under the given circumstances again. In our third main theorem we show that $mu$ can be chosen arbitrarily small as long as $mu > 0$ if, in addition to linear size induced subgraph having density $d > 0$ we also insist that every cut has density at least $mu$.

In fact Staden and Treglown showed that the graphs they consider do not just contain $k$-th powers of Hamiltonian cycles, but a broader class of graphs, namely graphs with bounded degree and sublinear bandwidth. The bandwidth of a graph is defined as the maximum distance of two vertices in a linear ordering of the vertices of a graph, where we take the minimum over all possible vertex orderings of the graph. In our fourth main theorem we show that we can keep this property for our relaxed assumptions.

In dieser Doktorarbeit befassen wir uns mit Strukturen in dichten Graphen. Im ersten Teil analysieren wir Zusammenhänge zwischen Minimalgradbedingungen und strukturellen Eigenschaften großer Graphen, die gewisse Teilgraphen nicht enthalten. Dies ist eines der zentralen Forschungsgebiete der extremalen Graphentheorie. Wir gehen näher auf den sogenannten $chromatic threshold$ ein, dieser ist wie folgt definiert. Für eine Familie $F**$ von Graphen sei der $chromatic threshold$ das Infimum aller $alpha in [0, 1]$, sodass jeder $F**$-freie graph $G$ auf $n$ Ecken mit Minimalgrad mindestens $alpha n$ ein homomorphes Bild $H$ begrenzter Größe hat. Anders ausgedrückt wollen wir die chromatische Zahl von $G$ durch eine Konstante $K(F**, alpha)$ beschränken. 2013 wurde der genaue $chromatic threshold$ für alle endlichen Familien $F**$ von Allen et al. bestimmt.

Bestehen wir jedoch darauf, dass auch das homomorphe Bild $H$ von $G$ selbst wieder $F**$-frei sein soll, so führt dies zur Definition des $homomorphic threshold$. Dieser ist bisher noch kaum verstanden, und unser erstes Haupttheorem bestimmt diesen für die Familie $C**(2k-1)$ der ungeraden Kreise bis zu einer länge von $2k-1$. In unserem zweiten Haupttheorem gehen wir noch genauer auf das homomorphe Bild $H$ ein um ein ausdifferenzierteres Bild von der Struktur von $G$ zu erhalten.

Im zweiten Teil untersuchen wir hinreichende Bedingungen für die Existenz $k$-ter Potenzen von Hamiltonkreisen in Graphen. Vor über 20 Jahren bestätigten Komlós, Sarközy und Szemerédi eine Vermutung von Pósa von 1964 und Seymour von 1973 indem sie zeigten, dass jeder Graph auf $n$ Ecken mit einem Minimalgrad von mindestens $mu n$ für $mu = k / k+1$ die $k$-te Potenz eines Hamiltonkreises enthält. Diese Schranke für $mu$ ist optimal. Staden und Treglown konnten 2018 jedoch zeigen, dass man $mu$ auf $1/2 + epsilon$ reduzieren kann, wenn man zusätzlich fordert, dass $G$ in induzierten Teilgraphen linearer Größe eine Dichte von wenigstens $d > 0$ aufweißt. Diese Schranke für $mu$ ist optimal für das erzwingen $k$-ter Potenzen von Hamiltonkreisen unter der gegebenen Nebenbedingung. In unserem dritten Haupttheorem zeigen wir, dass mit dem einführen einer zweiten Nebenbedingung, nämlich dass jeder Schnitt mindestens die Dichte $mu$ aufweist, $mu$ auf einen beliebig kleinen positiven Wert abgesenkt werden kann.

Tatsächlich zeigten Staden und Treglown in ihrem Artikel eine stärkere Aussage, und zwar das $G$ nicht nur die $k$-te Potenz eines Hamiltonkreises enthält, sondern jeden Graphen $H$ mit beschränktem Maximalgrad und sublinearer Bandweite. Die Bandweite eines Graphen ist dabei definiert als der maximale Abstand der Endecken einer Kante in einer linearen Ordnung der Ecken, wobei wir dies über alle linearen Ordnungen des Graphen minimieren. In unserem vierten Haupttheorem zeigen wir, dass wir diese Eigenschaft für $G$ auch mit unseren schwächeren Nebenbedingungen erzwingen können.