On the appearance of oriented trees in tournaments

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

Preview

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 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).

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):