{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:13869"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:13869","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Spanning and induced subgraphs in graphs and digraphs","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.","abstract_html":"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 <span class=\"etd-inline-math\">V<sub>1</sub>, \\ldots, V<sub>k</sub></span> each of size \\(n\\) and <span class=\"etd-inline-math\">&delta;(G[V<sub>i</sub>,V<sub>i+1</sub>]) \\geq (1 + 1/k) n/2</span>, then \\(G\\) contains a transversal <span class=\"etd-inline-math\">C<sub>k</sub></span>-factor, that is, a <span class=\"etd-inline-math\">C<sub>k</sub></span>-factor in which each copy of <span class=\"etd-inline-math\">C<sub>k</sub></span> 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 <span class=\"etd-inline-math\">C<sub>k</sub></span>-factor. This resolves a conjecture of Fischer for even \\(k\\). Our third result falls into the theory of edit distances. Let <span class=\"etd-inline-math\">C<sub>h</sub><sup>t</sup></span> 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 <span class=\"etd-inline-math\">\\text{Forb}(C<sub>h</sub><sup>t</sup>)</span> be the class of graphs with no induced copy of <span class=\"etd-inline-math\">C<sub>h</sub><sup>t</sup></span>. 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 <span class=\"etd-inline-math\">C<sub>h</sub><sup>t</sup></span>? The maximum of this quantity over all graphs of density \\(p\\) is measured by the edit distance function, <span class=\"etd-inline-math\">\\text{ed}<sub>\\text{Forb}(C<sub>h</sub><sup>t</sup>)</sub>(p)</span>, a function which provides a natural metric between graphs and hereditary properties. For our third result, we determine <span class=\"etd-inline-math\">\\text{ed}<sub>\\text{Forb}(C<sub>h</sub><sup>t</sup>)</sub>(p)</span> for all <span class=\"etd-inline-math\">p \\geq p<sub>0</sub></span> in the case when \\((t+1) \\mid h\\), where <span class=\"etd-inline-math\">p<sub>0</sub> = \\Theta(1/h<sup>2</sup>)</span>, thus improving on earlier work of Berikkyzy, Martin and Peck.","abstract_has_math":true,"creators":["Kathapurkar, Amarja"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-07","date_published":"2023-07","updated_at":"2026-11-19T09:32:22Z","subjects":["QA Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/13869/7/Kathapurkar2023PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A13869","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["epsrc"]},{"key":"dc:creator","label":"Author","values":["Kathapurkar, Amarja"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-07-12"]},{"key":"dc:date.issued","label":"Date","values":["2023-07"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/13869/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/13869/7/Kathapurkar2023PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["Spanning and induced subgraphs in graphs and digraphs"]}]}],"canonical_facts":{"dc:contributor.sponsor":["epsrc"],"dc:creator":["Kathapurkar, Amarja"],"dc:date":["2023-07-12"],"dc:date.issued":["2023-07"],"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 \\(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."],"dc:format":["text"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/13869/7/Kathapurkar2023PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Mathematics"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/13869/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public"],"dc:title":["Spanning and induced subgraphs in graphs and digraphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:32:22Z"}