Substructures in large graphs

Taylor, Amelia May (2017). Substructures in large graphs. University of Birmingham. Ph.D.

Preview

Taylor17PhD.pdf
PDF - Accepted Version
Download (1MB)

Abstract

The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.

We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs.

The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a K\(_r\)-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C\(_2\)\(_k\)-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):