School of Mathematical Sciences
Monday, April 11, 2016
Melamed Hall, 12:30
University of Waterloo
Matchings in hypergraphs
Abstract: A matching
in a hypergraph is a set of disjoint edges. While matchings in graphs
are very well understood, it is a well-known difficult problem to give
good lower bounds on the maximal size of a matching in a hypergraph in
terms of other natural parameters. We shall discuss tools for this,
with a focus on the special case of tripartite hypergraphs. For example, if a tripartite hypergraph is r-regular with n vertices in each class then it has a matching of size at least n/2, and this is tight for certain special hypergraphs. We investigate how this bound can be improved for all other hypergraphs.
Coffee will be served at 12:00 before the lecture
near Melamed Hall.
Even before, between 11:00-12:00, Gal Kronenberg will give an introductory talk, intended mainly for students without a firm background in combinatorics.