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.