Extremal problems in graphs

Hyde, Joseph Frederick (2021). Extremal problems in graphs. University of Birmingham. Ph.D.

Text - Accepted Version
Available under License Creative Commons Attribution No Derivatives.

Download (1MB) | Preview


In the first part of this thesis we will consider degree sequence results for graphs. An important result of Komlós [39] yields the asymptotically exact minimum degree threshold that ensures a graph \(G\) contains an \(H\)-tiling covering an \(x\)-proportion of the vertices of \(G\) (for any fixed \(x ∈\) (0, 1) and graph \(H\)). In Chapter 2, we give a degree sequence strengthening of this result. A fundamental result of Kühn and Osthus [46] determines up to an additive constant the minimum degree threshold that forces a graph to contain a perfect \(H\)-tiling. In Chapter 3, we prove a degree sequence version of this result.

We close this thesis in the study of asymmetric Ramsey properties in \(G_n,_p\). Specifically, for fixed graphs \(H_1, . . . , H_r,\) we study the asymptotic threshold function for the property \(G_n,_p\) → \(H_1, . . . , H_r\). Rödl and Ruciński [61, 62, 63] determined the threshold function for the general symmetric case; that is, when \(H_1 = · · · = H_r\). Kohayakawa and Kreuter [33] conjectured the threshold function for the asymmetric case. Building on work of Marciniszyn, Skokan, Spöhel and Steger [51], in Chapter 4, we reduce the 0-statement of Kohayakawa and Kreuter’s conjecture to a more approachable, deterministic conjecture. To demonstrate the potential of this approach, we show our conjecture holds for almost all pairs of regular graphs (satisfying certain balancedness conditions).

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Licence: Creative Commons: Attribution-No Derivative Works 4.0
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Mathematics
Funders: Engineering and Physical Sciences Research Council
Subjects: Q Science > QA Mathematics
URI: http://etheses.bham.ac.uk/id/eprint/12068


Request a Correction Request a Correction
View Item View Item


Downloads per month over past year