Skip to Content

Fundur í samstarfi við ICE-TCS

Föstudaginn, 2. september 2011 - 14:00
Háskólinn í Reykjavík, stofa V109

Ron Aharoni flytur fyrirlestur á sameiginlegum fundi Íslenska stærðfræðafélagsins og ICE-TCS stofnunarinnar í Háskólanum í Reykjavík. Fyrirlesturinn verður á ensku.

Titill: Matchings in hypergraphs - many problems and some results

Útdráttur: 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 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.

Staðsetning: Stofa V109 á fyrstu hæð Háskólans í Reykjavík við Nauthólsvík