{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:13792"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:13792","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"On the appearance of oriented trees in tournaments","abstract":"We consider how large a tournament must be in order to guarantee the appearance of a given oriented tree. Sumner’s universal tournament conjecture states that every (2\\(n\\)−2)-vertex tournament should contain a copy of every n-vertex oriented tree. However, it is known that improvements can be made over Sumner’s conjecture in some cases by considering the number of leaves or maximum degree of an oriented tree. To this end, we establish the following results. (1) There exists \\(C\\) > 0 such that any (\\(n\\) + \\(Ck\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (2) For each \\(k\\), there exists \\(n_0\\) ∈ \\(\\mathbb{N}\\), such that, whenever \\(n\\) ⩾ \\(n_0\\), any (\\(n\\)+\\(k\\) −2)-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with at most \\(k\\) leaves. (3) For every α > 0, there exists \\(n_0\\) ∈ \\( \\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any ((1+α)\\(n\\)+\\(k\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (4) For every α > 0, there exists \\(c\\) > 0 and \\(n_0\\) ∈ \\(\\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any (1 + α)\\(n\\)-vertex tournament contains a copy of any \\(n\\)-vertex oriented tree with maximum degree Δ(\\(T\\)) ⩽ \\(cn\\). (5) For all countably-infinite oriented graphs \\(H\\), either (i) there is a countably-infinite tournament not containing \\(H\\), or (ii) every countably-infinite tournament contains a spanning copy of \\(H\\). (1) improves the previously best known bound of \\(n\\) + \\(O(k^2)\\). (2) confirms a conjecture of Dross and Havet. (3) provides an asymptotic form of a conjecture of Havet and Thomassé. (4) improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree. (5) extends the problem to the infinite setting, where we also consider sufficient conditions for the appearance of oriented graphs satisfying (i).","abstract_html":"We consider how large a tournament must be in order to guarantee the appearance of a given oriented tree. Sumner’s universal tournament conjecture states that every (2\\(n\\)−2)-vertex tournament should contain a copy of every n-vertex oriented tree. However, it is known that improvements can be made over Sumner’s conjecture in some cases by considering the number of leaves or maximum degree of an oriented tree. To this end, we establish the following results. (1) There exists \\(C\\) &gt; 0 such that any (\\(n\\) + \\(Ck\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (2) For each \\(k\\), there exists <span class=\"etd-inline-math\">n<sub>0</sub></span> ∈ \\(\\mathbb{N}\\), such that, whenever \\(n\\) ⩾ <span class=\"etd-inline-math\">n<sub>0</sub></span>, any (\\(n\\)+\\(k\\) −2)-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with at most \\(k\\) leaves. (3) For every α &gt; 0, there exists <span class=\"etd-inline-math\">n<sub>0</sub></span> ∈ \\( \\mathbb{N}\\) such that, whenever \\(n\\) ⩾ <span class=\"etd-inline-math\">n<sub>0</sub></span>, any ((1+α)\\(n\\)+\\(k\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (4) For every α &gt; 0, there exists \\(c\\) &gt; 0 and <span class=\"etd-inline-math\">n<sub>0</sub></span> ∈ \\(\\mathbb{N}\\) such that, whenever \\(n\\) ⩾ <span class=\"etd-inline-math\">n<sub>0</sub></span>, any (1 + α)\\(n\\)-vertex tournament contains a copy of any \\(n\\)-vertex oriented tree with maximum degree Δ(\\(T\\)) ⩽ \\(cn\\). (5) For all countably-infinite oriented graphs \\(H\\), either (i) there is a countably-infinite tournament not containing \\(H\\), or (ii) every countably-infinite tournament contains a spanning copy of \\(H\\). (1) improves the previously best known bound of \\(n\\) + <span class=\"etd-inline-math\">O(k<sup>2</sup>)</span>. (2) confirms a conjecture of Dross and Havet. (3) provides an asymptotic form of a conjecture of Havet and Thomassé. (4) improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree. (5) extends the problem to the infinite setting, where we also consider sufficient conditions for the appearance of oriented graphs satisfying (i).","abstract_has_math":true,"creators":["Benford, Alistair"],"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/13792/7/Benford2023PhD.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%3A13792","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["epsrc"]},{"key":"dc:creator","label":"Author","values":["Benford, Alistair"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-07"]},{"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/13792/"]},{"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/13792/7/Benford2023PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We consider how large a tournament must be in order to guarantee the appearance of a given oriented tree. Sumner’s universal tournament conjecture states that every (2\\(n\\)−2)-vertex tournament should contain a copy of every n-vertex oriented tree. However, it is known that improvements can be made over Sumner’s conjecture in some cases by considering the number of leaves or maximum degree of an oriented tree. To this end, we establish the following results. (1) There exists \\(C\\) > 0 such that any (\\(n\\) + \\(Ck\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (2) For each \\(k\\), there exists \\(n_0\\) ∈ \\(\\mathbb{N}\\), such that, whenever \\(n\\) ⩾ \\(n_0\\), any (\\(n\\)+\\(k\\) −2)-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with at most \\(k\\) leaves. (3) For every α > 0, there exists \\(n_0\\) ∈ \\( \\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any ((1+α)\\(n\\)+\\(k\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (4) For every α > 0, there exists \\(c\\) > 0 and \\(n_0\\) ∈ \\(\\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any (1 + α)\\(n\\)-vertex tournament contains a copy of any \\(n\\)-vertex oriented tree with maximum degree Δ(\\(T\\)) ⩽ \\(cn\\). (5) For all countably-infinite oriented graphs \\(H\\), either (i) there is a countably-infinite tournament not containing \\(H\\), or (ii) every countably-infinite tournament contains a spanning copy of \\(H\\). (1) improves the previously best known bound of \\(n\\) + \\(O(k^2)\\). (2) confirms a conjecture of Dross and Havet. (3) provides an asymptotic form of a conjecture of Havet and Thomassé. (4) improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree. (5) extends the problem to the infinite setting, where we also consider sufficient conditions for the appearance of oriented graphs satisfying (i)."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["On the appearance of oriented trees in tournaments"]}]}],"canonical_facts":{"dc:contributor.sponsor":["epsrc"],"dc:creator":["Benford, Alistair"],"dc:date":["2023-07"],"dc:date.issued":["2023-07"],"dc:description.abstract":["We consider how large a tournament must be in order to guarantee the appearance of a given oriented tree. Sumner’s universal tournament conjecture states that every (2\\(n\\)−2)-vertex tournament should contain a copy of every n-vertex oriented tree. However, it is known that improvements can be made over Sumner’s conjecture in some cases by considering the number of leaves or maximum degree of an oriented tree. To this end, we establish the following results. (1) There exists \\(C\\) > 0 such that any (\\(n\\) + \\(Ck\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (2) For each \\(k\\), there exists \\(n_0\\) ∈ \\(\\mathbb{N}\\), such that, whenever \\(n\\) ⩾ \\(n_0\\), any (\\(n\\)+\\(k\\) −2)-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with at most \\(k\\) leaves. (3) For every α > 0, there exists \\(n_0\\) ∈ \\( \\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any ((1+α)\\(n\\)+\\(k\\))-vertex tournament contains a copy of every \\(n\\)-vertex oriented tree with \\(k\\) leaves. (4) For every α > 0, there exists \\(c\\) > 0 and \\(n_0\\) ∈ \\(\\mathbb{N}\\) such that, whenever \\(n\\) ⩾ \\(n_0\\), any (1 + α)\\(n\\)-vertex tournament contains a copy of any \\(n\\)-vertex oriented tree with maximum degree Δ(\\(T\\)) ⩽ \\(cn\\). (5) For all countably-infinite oriented graphs \\(H\\), either (i) there is a countably-infinite tournament not containing \\(H\\), or (ii) every countably-infinite tournament contains a spanning copy of \\(H\\). (1) improves the previously best known bound of \\(n\\) + \\(O(k^2)\\). (2) confirms a conjecture of Dross and Havet. (3) provides an asymptotic form of a conjecture of Havet and Thomassé. (4) improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree. (5) extends the problem to the infinite setting, where we also consider sufficient conditions for the appearance of oriented graphs satisfying (i)."],"dc:format":["text"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/13792/7/Benford2023PhD.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/13792/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public"],"dc:title":["On the appearance of oriented trees in tournaments"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:32:22Z"}