Large structures in dense directed graphs

Naia dos Santos, Tassio (2018). Large structures in dense directed graphs. University of Birmingham. Ph.D.

[img]
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):
Supervisor(s)EmailORCID
Mycroft, RichardUNSPECIFIEDUNSPECIFIED
Osthus, DerykUNSPECIFIEDUNSPECIFIED
Licence:
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Mathematics
Funders: Other
Other Funders: Science without Borders, Brazilian National Council for Scientific and Technological Development
Subjects: Q Science > QA Mathematics
URI: http://etheses.bham.ac.uk/id/eprint/8658

Actions

Request a Correction Request a Correction
View Item View Item

Downloads

Downloads per month over past year