TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 16.06.2016

isti-logo

Page Content

to Navigation

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.

 

Date
Speaker
Location
Language
16.06.2016
16:15
Ruth Bosse
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe