Combinatorics Seminar
Richard Mycroft
Birmingham
Packing k-partite k-graphs
Abstract: Let G and H be graphs or hypergraphs. A perfect H-packing in G is a
collection of vertex-disjoint copies of H in G which together cover
every vertex of G. In the simplest case, where H is the graph consisting
of a single edge, a perfect H-packing in G is simply a perfect matching
in G; Dirac's theorem tells us that such a packing must exist if G has
minimum degree at least n/2 (where n is the number of vertices of G).
The problem of what minimum degree is needed to ensure a perfect
H-packing in G for general graphs H was then tackled by many
researchers, before K\"uhn and Osthus finally established the correct
threshold for all graphs H (up to an additive constant).
However, for k-uniform hypergraphs (or k-graphs) much less is known. The
case of a perfect matching has been well-studied, but apart from this
there were previously no known asymptotically correct results on the
minimum degree needed to ensure a perfect H-packing in G for k > 4 (for
any of the various common generalisations of the notion of degree to the
k-graph setting).
In this talk I will demonstrate, for any complete k-partite k-graph H,
the asymptotically best-possible minimum codegree condition for a
k-graph G which ensures that G contains a perfect H-packing. This
condition depends on the sizes of the vertex classes of H, and whether
these sizes, or their differences, share any common factors greater than
one.
Wednesday April 2, 2014 at 3:00 PM in SEO 427