direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Ryser's Conjecture on Matchings in Hypergraphs

Ruth Bosse (TU Berlin)


P. Haxell and A. Scott showed that in any k-partite k-uniform hypergraph, the size of a minimum cover is at most (k − ε) times the size of a maximum matching for some ε>0 and k ∈ {4, 5}. They published their proof in the article “On Ryser’s Conjecture“ [Electronic Journal of Combinatorics, 2012]. This theorem approximates some cases of the well-known conjecture of Ryser. Until now, only a few cases of this conjecture have been proved.

My talk will sketch the proof of Haxell and Scott. Furthermore, it will give an introduction to vertex covers and matchings in hypergraphs and show the background and some applications of Ryser’s Conjecture. I will also call attention to the sunflower picking procedure, which is used to kernelize problems and reduce big data structures.


Ruth Bosse
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras