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

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): 


Licence:  All rights reserved  
College/Faculty:  Colleges (2008 onwards) > College of Engineering & Physical Sciences  
School or Department:  School of Mathematics  
Funders:  Engineering and Physical Sciences Research Council  
Subjects:  Q Science > QA Mathematics  
URI:  http://etheses.bham.ac.uk/id/eprint/13869 
Actions
Request a Correction  
View Item 
Downloads
Downloads per month over past year