Queen Mary, University of London
Matching and Packing
Abstract: Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. In this talk I will aim to show some of the breadth of the subject, and some recent advances on matching theory for hypergraphs (joint work with Richard Mycroft). Informally speaking, we show that the obstructions to perfect matchings are geometric, and are of two distinct types: `space barriers' from convex geometry, and `divisibility barriers' from arithmetic lattice-based constructions. We apply our theory to the solution of two open problems on hypergraph packings: the minimum degree threshold for packing tetrahedra in 3-graphs, and Fischer's conjecture on a multipartite form of the Hajnal-Szemeredi Theorem.
Friday February 17, 2012 at 3:00 PM in SEO 636