LUCA ACETO
Deildarforseti tölvunarfræðideildar
Viðburðir
ICE-TCS Lectures Series - Ron Aharoni - Matchings in hypergraphs - many problems and some results
On Friday, 2 September, Ron Aharoni (Technion, Israel) will deliver a talk entitled "Matchings in hypergraphs - many problems and some results".
The talk, which will be held at 2pm in room V109 at Reykjavik University, is organized jointly by ICE-TCS and the Icelandic Mathematical Society.
The lecture is free and open to everyone.
ABSTRACT
A graph is a collection of pairs; a hypergraph is a collection of finite sets of arbitrary size, called the "edges" of the hypergraph. A
matching is a collection of disjoint edges. Graph matchings are well understood - for example there are min-max
formulas for the maximal size of a matching in a graph, and there is a polynomial time algorithm for finding a maximal matching. The
situation in hypergraphs matchings is very different. Most problems are algorithmically NP hard, there are many fascinating conjectures, and not so many results. I will describe the main conjectures, and some results. Based in part on joint work with David Howard.
