On the complexity of Ryser's Conjecture

Jul 23, 2016

Sprecher:innen

Über

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.

Organisator

Kategorien

Über The Mathematics of Jiří Matoušek

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

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? The Mathematics of Jiří Matoušek folgen