Benford, Alistair (2023). On the appearance of oriented trees in tournaments. University of Birmingham. Ph.D.

Benford2023PhD.pdf
Text Available under License All rights reserved. Download (1MB)  Preview 
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 nvertex 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 countablyinfinite oriented graphs \(H\), either (i) there is a countablyinfinite tournament not containing \(H\), or (ii) every countablyinfinite 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).
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/13792 
Actions
Request a Correction  
View Item 
Downloads
Downloads per month over past year