Tel-Aviv University
School of Mathematical Sciences

Department Colloquium

Monday, April 11, 2016

Melamed Hall, 12:30

Penny Haxell

University of Waterloo

Matchings in hypergraphs

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.