On the complexity of Ryser's Conjecture

by · Jul 23, 2016 · 202 views ·

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.

Watch SlidesLive on mobile devices

© SlidesLive Inc.