Embeddings of cycle-like structures

Abstract

In this thesis we focus on problems in Extremal and Probabilistic Combinatorics. The thesis is organized in three parts, each concerning a problem regarding sufficient conditions for a host graph to contain some cycle-like subgraph.

In the first and main part, we want to embed spanning tripartite graphs with small linear bandwidth and bounded maximum degree. This continues a previous joint work with Ebsen et al., in which the conditions required for the host graph are uniform density in linear sized subsets of vertices and a small density in every cut. Even though this previous result applies to graph with arbitrarily small linear minimum degree, the classical degree condition of the bandwidth theorem of Böttcher, Schacht and Taraz, does not ensure the uniform density condition. Here we relax this notion of uniform density by requiring instead a robust almost perfect fractional triangle factor in the host graph, aiming for a common generalisation of both results. This and more general results were shown independently in a recent work of Lang and Sanhueza-Matamala.

In the second part, we study the multi-colour size-Ramsey number of powers of bounded degree trees. This parameter is the smallest number of edges in a host graph with the property that for any colouring of its edges with a fixed number of colours, there is a monocromatic copy of the given power of tree. We prove that this parameter is linear on the number of vertices of the tree. As a corollary we obtain that the multi-colour size-Ramsey number of graphs with bounded treewidth and bounded degree is linear on its number of vertices, which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan.

In the third part, we are interested in the model of randomly perturbed graphs that consider the union of a deterministic graph with linear minimum degree and the binomial random graph. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the works of Posá and Koršunov on the threshold in the binomial random graph. We extend this result in the perturbed model to sparser graphs with minimum degree tending to zero. We also discuss embeddings of bounded degree trees and other spanning structures in this model. This leads to interesting questions on almost spanning embeddings in the binomial random graph.