{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:4027"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:4027","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Embedding spanning structures in graphs and hypergraphs","abstract":"In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log\\(^5\\)\\(^0\\) n/n \\ ≤ p ≤ 1 – n \\(^-\\)\\(^1\\)\\(^/\\)\\(^4\\) log\\(^9\\) n, a binomial random graph G ~ G\\(_n\\)\\(_,\\)\\(_p\\) contains with high probability a collection of └\\(\\delta\\)(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if \\(\\delta\\)(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any `robustly expanding' graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + \\(\\eta\\))n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for \\(\\gamma\\) > 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + \\(\\gamma\\))n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games.","abstract_html":"In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log<span class=\"etd-inline-math\"><sup>5</sup></span><span class=\"etd-inline-math\"><sup>0</sup></span> n/n \\ ≤ p ≤ 1 – n <span class=\"etd-inline-math\"><sup>-</sup></span><span class=\"etd-inline-math\"><sup>1</sup></span><span class=\"etd-inline-math\"><sup>/</sup></span><span class=\"etd-inline-math\"><sup>4</sup></span> log<span class=\"etd-inline-math\"><sup>9</sup></span> n, a binomial random graph G ~ G<span class=\"etd-inline-math\"><sub>n</sub></span><span class=\"etd-inline-math\"><sub>,</sub></span><span class=\"etd-inline-math\"><sub>p</sub></span> contains with high probability a collection of └<span class=\"etd-inline-math\">&delta;</span>(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if <span class=\"etd-inline-math\">&delta;</span>(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any `robustly expanding&#x27; graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + \\(\\eta\\))n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for <span class=\"etd-inline-math\">&gamma;</span> &gt; 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + <span class=\"etd-inline-math\">&gamma;</span>)n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games.","abstract_has_math":true,"creators":["Knox, Fiachra"],"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":2013,"date_issued":"2013-07","date_published":"2013-07","updated_at":"2026-11-19T09:27:30Z","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/4027/1/Knox13PhD.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%3A4027","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["epsrc"]},{"key":"dc:creator","label":"Author","values":["Knox, Fiachra"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-07"]},{"key":"dc:date.issued","label":"Date","values":["2013-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/4027/"]},{"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/4027/1/Knox13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4027/2/Decl_IS_Knox13PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log\\(^5\\)\\(^0\\) n/n \\ ≤ p ≤ 1 – n \\(^-\\)\\(^1\\)\\(^/\\)\\(^4\\) log\\(^9\\) n, a binomial random graph G ~ G\\(_n\\)\\(_,\\)\\(_p\\) contains with high probability a collection of └\\(\\delta\\)(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if \\(\\delta\\)(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any `robustly expanding' graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + \\(\\eta\\))n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for \\(\\gamma\\) > 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + \\(\\gamma\\))n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public","staffonly"]},{"key":"dc:title","label":"Title","values":["Embedding spanning structures in graphs and hypergraphs"]}]}],"canonical_facts":{"dc:contributor.sponsor":["epsrc"],"dc:creator":["Knox, Fiachra"],"dc:date":["2013-07"],"dc:date.issued":["2013-07"],"dc:description.abstract":["In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log\\(^5\\)\\(^0\\) n/n \\ ≤ p ≤ 1 – n \\(^-\\)\\(^1\\)\\(^/\\)\\(^4\\) log\\(^9\\) n, a binomial random graph G ~ G\\(_n\\)\\(_,\\)\\(_p\\) contains with high probability a collection of └\\(\\delta\\)(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if \\(\\delta\\)(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any `robustly expanding' graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + \\(\\eta\\))n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for \\(\\gamma\\) > 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + \\(\\gamma\\))n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/4027/1/Knox13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4027/2/Decl_IS_Knox13PhD.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/4027/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public","staffonly"],"dc:title":["Embedding spanning structures in graphs and hypergraphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:27:30Z"}