Spanning and induced subgraphs in graphs and digraphs

Kathapurkar, Amarja (2023). Spanning and induced subgraphs in graphs and digraphs. University of Birmingham. Ph.D.

Preview

Kathapurkar2023PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (1MB) | Preview

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 \(V_1, \ldots, V_k\) each of size \(n\) and \(\delta(G[V_i,V_{i+1}]) \geq (1 + 1/k) n/2\), then \(G\) contains a transversal \(C_k\)-factor, that is, a \(C_k\)-factor in which each copy of \(C_k\) 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 \(C_k\)-factor. This resolves a conjecture of Fischer for even \(k\).

Our third result falls into the theory of edit distances. Let \(C_h^t\) 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}(C_h^t)\) be the class of graphs with no induced copy of \(C_h^t\). 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 \(C_h^t\)? The maximum of this quantity over all graphs of density \(p\) is measured by the edit distance function, \(\text{ed}_{\text{Forb}(C_h^t)}(p)\), a function which provides a natural metric between graphs and hereditary properties. For our third result, we determine \(\text{ed}_{\text{Forb}(C_h^t)}(p)\) for all \(p \geq p_0\) in the case when \((t+1) \mid h\), where \(p_0 = \Theta(1/h^2)\), thus improving on earlier work of Berikkyzy, Martin and Peck.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):