School of Mathematical Sciences

Department Colloquium

Melamed Hall, 12:30

University of Waterloo

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.

Abstract:

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.