{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:7241"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:7241","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Substructures in large graphs","abstract":"The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason. We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs. The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a K\\(_r\\)-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C\\(_2\\)\\(_k\\)-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied.","abstract_html":"The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason. We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs. The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a K<span class=\"etd-inline-math\"><sub>r</sub></span>-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C<span class=\"etd-inline-math\"><sub>2</sub></span><span class=\"etd-inline-math\"><sub>k</sub></span>-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied.","abstract_has_math":true,"creators":["Taylor, Amelia May"],"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":2017,"date_issued":"2017-07","date_published":"2017-07","updated_at":"2026-11-19T09:29:14Z","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/7241/1/Taylor17PhD.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%3A7241","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["na"]},{"key":"dc:creator","label":"Author","values":["Taylor, Amelia May"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-07"]},{"key":"dc:date.issued","label":"Date","values":["2017-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/7241/"]},{"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/7241/1/Taylor17PhD.pdf","http://etheses.bham.ac.uk//id/eprint/7241/2/Decl_IS_Taylor17PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason. We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs. The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a K\\(_r\\)-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C\\(_2\\)\\(_k\\)-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public","staffonly"]},{"key":"dc:title","label":"Title","values":["Substructures in large graphs"]}]}],"canonical_facts":{"dc:contributor.sponsor":["na"],"dc:creator":["Taylor, Amelia May"],"dc:date":["2017-07"],"dc:date.issued":["2017-07"],"dc:description.abstract":["The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason. We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs. The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a K\\(_r\\)-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C\\(_2\\)\\(_k\\)-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/7241/1/Taylor17PhD.pdf","http://etheses.bham.ac.uk//id/eprint/7241/2/Decl_IS_Taylor17PhD.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/7241/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public","staffonly"],"dc:title":["Substructures in large graphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:29:14Z"}