Back to search

University of Birmingham

Spanning and induced subgraphs in graphs and digraphs

Abstract

dc:description.abstract

In 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 × 1

Rights

Language dc:language.dcterms_iso639_2
eng

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

Kathapurkar, Amarja. Spanning and induced subgraphs in graphs and digraphs. d_ph thesis, University of Birmingham, 2023.