Back to search

University of Birmingham

Extremal problems in graphs

Abstract

dc:description.abstract

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 Gn,p. Specifically, for fixed graphs H1, . . . , Hr, we study the asymptotic threshold function for the property Gn,p → H1, . . . , Hr. Rödl and Ruciński [61, 62, 63] determined the threshold function for the general symmetric case; that is, when H1 = · · · = Hr. 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).

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hyde, Joseph Frederick

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Dc Identifier Grantnumber
Extremal problems for graphs and the integers - 1935869

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hyde, Joseph Frederick. Extremal problems in graphs. d_ph thesis, University of Birmingham, 2021.