Tölvunarfræðideild

Viðburðir

ICE-TCS Lectures Series - Ron Aharoni - Matchings in hypergraphs - many problems and some results

  • 2.9.2011, 14:00 - 15:00

ICE-TCS-logo-vertical-basic-100pxOn 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.