We consider the parameter $a(H)$, which is the smallest a such that if $|E(G)|$ is at least/exceeds $a|V(H)|/2$ then $G$ has an $H$-minor. We are especially interested in sparse $H$ and in bounding $a(H)$ as a function of $|E(H)|$ and $|V(H)|$. This is joint work with David Wood.
Perfect matchings are fundamental objects of study in graph theory. There is a substantial classical theory, which cannot be directly generalised to hypergraphs unless P=NP, as it is NP-complete to determine whether a hypergraph has a perfect matching. On the other hand, the generalisation to hypergraphs is well-motivated, as many important problems can be recast in this framework, such as Ryser's conjecture on transversals in latin squares and the Erdos-Hanani conjecture on the existence of designs. We will discuss a characterisation of the perfect matching problem for uniform hypergraphs that satisfy certain density conditions (joint work with Richard Mycroft), and a polynomial time algorithm for determining whether such hypergraphs have a perfect matching (joint work with Fiachra Knox and Richard Mycroft).
An independent set in an $r$-uniform hypergraph is a subset of the vertices
that contains no edges. A container for the independent set is a superset
of it. It turns out to be desirable for many applications to find a small
collection of containers, none of which is large, but which between them
contain every independent set. ("Large" and "small" have reasonable
meanings which will be explained.)
Applications include giving bounds on the list chromatic number of
hypergraphs (including improving known bounds for graphs), counting the
solutions to equations in Abelian groups, counting Sidon sets,
establishing extremal properties of random graphs, etc.
The work is joint with David Saxton.