Large structures in dense directed graphs

Naia dos Santos, Tassio ORCID: 0000-0003-3158-4523 (2018). Large structures in dense directed graphs. University of Birmingham. Ph.D.

Preview

NaiadosSantos18PhD.pdf
PDF
Download (1MB)

Abstract

We answer questions in extremal combinatorics, for directed graphs. Specifically, we investigate which large tree-like directed graphs are contained in all dense directed graphs of large order. More precisely, let T be an oriented tree of order n; among others, we establish the following results.

(1) We obtain a sufficient condition which ensures every tournament of order n contains T, and show that almost every tree possesses this property.
(2) We prove that for all positive C, ɛ and sufficiently large n, every tournament of order (1+ɛ)n contains T if Δ(T)≤(log n)^C.
(3) We prove that for all positive Δ, ɛ and sufficiently large n, every directed graph G of order n and minimum semidegree (1/2+ɛ)n contains T if Δ(T)≤Δ.
(4) We obtain a sufficient condition which ensures that every directed graph G of order n with minimum semidegree at least (1/2+ɛ)n contains T, and show that almost every tree possesses this property.
(5) We extend our method in (4) to a class of tree-like spanning graphs which includes all orientations of Hamilton cycles and large subdivisions of any graph.

Result (1) confirms a conjecture of Bender and Wormald and settles a conjecture of Havet and Thomassé for almost every tree; (2) strengthens a result of Kühn, Mycroft and Osthus; (3) is a directed graph analogue of a classical result of Komlós, Sárközy and Szemerédi and is implied by (4) and (5) is of independent interest.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):