On the complexity of Ryser's Conjecture

Jul 23, 2016

Speakers

About

Ryser's Conjecture states that for every rr-partite rr-uniform hypergraph it is possible to find a vertex cover of size only (r−1)(r−1)-times the matching number. For r=2r=2, the conjecture reduces to König's Theorem, for r=3r=3 it was proved by Aharoni by topolgical methods, while for larger rr it is wide open. In the talk we will be focusing on those hypergraphs that are extremal for Ryser's Conjecture, that is their vertex cover number is exactly (r−1)(r−1)-times their matching number. An intricate extension of Aharoni's topological method (obtained with Penny Haxell and Lothar Narins) provides a characterization of the 33-uniform Ryser-extremal hypergraphs. In the talk we describe a recent joint work with Ahmad Abu-Khazneh, János Barát, and Alexey Pokrovskiy, where we construct exponentially many non-isomorphic Ryser-extremal hypergraphs, for a new infinite sequence of uniformities rr. We speculate that these constructions provide further evidence that Ryser's Conjecture, if true in general, will not be solved by purely combinatorial methods.

Organizer

Categories

About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek