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.

Back to the research colloquium site.