PhD Thesis

My PhD thesis, Connectivity, tree-decompositions and unavoidable-minors, was in the field of Graph Theory. I proved that any very large graphs is either made by attaching smaller graphs in a particular way, or contains a certain kind of substructure, illustrated here.

For those who are curious, I've included the abstract, and a link to the full thesis.

Abstract

The results in this thesis are steps toward bridging the gap between the handful of
exact structure theorems known for minor-closed classes of graphs, and the very general,
yet wildly qualitative, Graph Minors Structure Theorem.

This thesis introduces a refinement of the notion of tree-width. Tree-width is a measure
of how “tree-like” a graph is. Essentially, a graph is tree-like if it can be decomposed across
a collection of non-crossing vertex-separations into small pieces. In our variant, which we
call k-tree-width, we require that the vertex-separations each have order at most k.

Tree-width and branch-width are related parameters in a graph, and we introduce a
branch-width-like variant for k-tree-width. We find a dual notion, in terms of tangles, for
our branch-width parameter, and we prove a generalization of Robertson and Seymour’s
Grid Theorem.

Download thesis (PDF)