Packing and embedding large subgraphs

Condon, Padraig (2020). Packing and embedding large subgraphs. University of Birmingham. Ph.D.

Preview

Condon2020PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (2MB) | Preview

Abstract

This thesis contains several embedding results for graphs in both random and non random settings.
Most notably, we resolve a long standing conjecture that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. %posed e.g.~by Bollob\'as,

In Chapter 2 we obtain the following perturbation result regarding the hypercube $\cQ^n$:
if $H\subseteq\cQ^n$ satisfies $\delta(H)\geq\alpha n$ with $\alpha>0$ fixed and we consider a random binomial subgraph $\cQ^n_p$ of $\cQ^n$ with $p\in(0,1]$ fixed, then with high probability $H\cup\cQ^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$.
This result is part of a larger volume of work where we also prove the corresponding hitting time result for Hamiltonicity.

In Chapter 3 we move to a non random setting. %to a deterministic one.
%Instead of embedding a single Hamilton cycle our result concerns packing more general families of graphs into a fixed host graph.
Rather than pack a small number of Hamilton cycles into a fixed host graph, our aim is to achieve optimally sized packings of more general families of graphs.
More specifically, we provide a degree condition on a regular $n$-vertex graph $G$ which ensures the existence of a near optimal packing of any family $\mathcal H$ of bounded degree $n$-vertex $k$-chromatic separable graphs into $G$.
%In general, this degree condition is best possible.
%In particular, this yields an approximate version of the tree packing conjecture
%in the setting of regular host graphs $G$ of high degree.
%Similarly, our result implies approximate versions of the Oberwolfach problem,
%the Alspach problem and the existence of resolvable designs in the setting of
%regular host graphs of high degree.
In particular, this yields approximate versions of the the tree packing conjecture, the Oberwolfach problem,
the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):