Abstract
dc:description.abstractIn this thesis, we make progress on three problems in extremal combinatorics, particularly in relation to finding large spanning subgraphs, and removing induced subgraphs. First, we prove a generalisation of a result of Komlós, Sárközy and Szemerédi and show that for \(n\) sufficiently large, any \(n\)-vertex digraph with minimum semidegree at least \(n/2 + o(n)\) contains a copy of every \(n\)-vertex oriented tree with underlying maximum degree at most \(O(n/\log n)\). For our second result, we prove that when \(k\) is an even integer and \(n\) is sufficiently large, if \(G\) is a \(k\)-partite graph with vertex classes V1, \ldots, Vk each of size \(n\) and δ(G[Vi,Vi+1]) \geq (1 + 1/k) n/2, then \(G\) contains a transversal Ck-factor, that is, a Ck-factor in which each copy of Ck contains exactly one vertex from each vertex class. In the case when \(k\) is odd, we reduce the problem to proving that when \(G\) is close to a specific extremal structure, it contains a transversal Ck-factor. This resolves a conjecture of Fischer for even \(k\). Our third result falls into the theory of edit distances. Let Cht be the \(t\)-th power of a cycle of length \(h\), that is, a cycle of length \(h\) with additional edges between vertices at distance at most \(t\) on the cycle. Let \text{Forb}(Cht) be the class of graphs with no induced copy of Cht. For \(p \in [0,1]\), what is the minimum proportion of edges which must be added to or removed from a graph of density \(p\) to eliminate all induced copies of Cht? The maximum of this quantity over all graphs of density \(p\) is measured by the edit distance function, \text{ed}\text{Forb}(Cht)(p), a function which provides a natural metric between graphs and hereditary properties. For our third result, we determine \text{ed}\text{Forb}(Cht)(p) for all p \geq p0 in the case when \((t+1) \mid h\), where p0 = \Theta(1/h2), thus improving on earlier work of Berikkyzy, Martin and Peck.
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
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kathapurkar, Amarja
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng