Extremal Hypergraphs for Ryser's Conjecture

Abstract

Ryser's Conjecture from the year 1971 is that the inequality $\tau(\mathcal{H}) \leq (r - 1)\nu(\mathcal{H})$ holds for every $r$-partite $r$-uniform hypergraph $\mathcal{H}$, where $\tau(\mathcal{H})$ and $\nu(\mathcal{H})$ represent the vertex cover number and the matching number, respectively. The conjecture is still wide open, though advances in various directions have been made by Aharoni, Berger, F\"uredi, Haxell, Lov{\'a}sz, Mansour, Scott, Song, Tuza, Yuster, and Ziv, among others. In 1999, Aharoni gave a proof of the conjecture for the case $r = 3$. The main result of this thesis is the characterization of all $3$-partite $3$-uniform hypergraphs $\mathcal{H}$ for which $\tau(\cmathcal{H}) = 2\nu(\mathcal{H})$, in other words, the extremal hypergraphs for Ryser's Conjecture for $r = 3$. These all have a special form, which we call "home-base" hypergraphs. They consist of $\nu(\mathcal{H})$ subhypergraphs, each with $\tau = 2$ and $\nu = 1$, together with possibly some extra hyperedges that intersect these parts in a very particular fashion. Along the way towards the proof of this characterization, we also find a characterization of all bipartite graphs that are extremal for a certain topological problem. For both characterizations, we utilize knowledge about the topology of the independence complex $\mathcal{I}$ of line graphs. For this reason, we next investigate a lower bound on the connectedness of $\mathcal{I}(L(\mathcal{H}))$ with respect to $\tau(\mathcal{H})$. We conjecture that this bound can be improved in the case of $r$-partite $r$-uniform hypergraphs, and we verify the conjecture for the special cases $r = 3$ and $\tau(\mathcal{H}) \leq 12$. A theorem of Meshulam that concerns the connectedness of the independence complex of a graph plays an important role in our proofs. The proof of this theorem that one finds in the literature is rather algebraic. We give a more geometric proof using certain triangulation techniques. The correctness of these methods, which were used for instance by Szab\'o and Tardos, has recently come into question. In the last part of this thesis, we provide a thorough proof of their correctness.

Rysers Vermutung aus dem Jahre 1971 besagt, dass f\"ur einen $r$-partiten $r$-uniformen Hypergraphen $\mathcal{H}$ die Ungleichung $\tau(\mathcal{H}) \leq (r - 1)\nu(\mathcal{H})$ erf\"ullt ist, wobei $\tau(\mathcal{H})$ die Knoten\"uberdeckungzahl und $\nu(\mathcal{H})$ die Matchingzahl bezeichnet. Diese Vermutung ist im Allgemeinen weiterhin offen. Fortschritte in verschiedenen Richtungen gab es unter anderem von Aharoni, Berger, F\"uredi, Haxell, Lov{\'a}sz, Mansour, Scott, Song, Tuza, Yuster, und Ziv. Im Spezialfall $r = 3$ hat Aharoni die Vermutung im Jahre 1999 bewiesen. Das Hauptthema dieser Dissertation ist die Charakterisierung aller tripartiten $3$-uniformen Hypergraphen $\mathcal{H}$, die $\tau(\mathcal{H}) = 2\nu(\mathcal{H})$ erf\"ullen, also der extremalen Hypergraphen f\"ur Rysers Vermutung f\"ur $r = 3$. Diese haben alle eine besondere Form, die wir ``Home- Base'' Hypergraphen nennen. Sie bestehen im Grunde aus $\nu(\mathcal{H})$ Teilhypergraphen mit $\tau = 2$ und $\nu = 1$, zusammen mit m\"oglicherweise extra Hyperkanten, die diese Teile nur auf bestimmte Weise schneiden. Auf dem Weg zu einem Beweis dieser Charakterisierung finden wir auch eine Charakterisierung von bipartiten Graphen, die extremal f\"ur ein bestimmtes topologisches Problem sind. F\"ur beide Charakterisierungen benutzen wir Kenntnisse \"uber die Topologie des sogenannten ``Independence Complex'' $\mathcal{I}$ von Kantengraphen. Deshalb untersuchen wir zun\"achst eine untere Schranke des Zusammenhangs von $\mathcal{I}(L(\mathcal{H}))$ in Abh\"angigkeit von $\tau(\mathcal{H})$. Wir vermuten, dass diese Schranke verbessert werden kann f\"ur $r$-partite $r$-uniforme Hypergraphen, und best\"atigen diese Vermutung f\"ur den Spezialfall $r = 3$ und $\tau(\mathcal{H}) \leq 12$. Ein Satz von Meshulam, welcher eine Aussage \"uber den Zusammenhang von dem ``Independence Complex'' eines Graphen macht, spielt eine wichtige Rolle in unseren Beweisen. Der Beweis dieses Satzes den man in der Literatur findet ist algebraisch gepr\"agt. Wir geben einen eher geometrischen Beweis, in dem wir bestimmte Triangulierungsmethoden benutzen. Die Richtigkeit dieser Methoden, die unter anderem von Szab\'o und Tardos benutzt werden, wurde vor ein paar Jahren in Frage gestellt. Im letzten Teil dieser Dissertation liefern wir einen ausf\"uhrlichen Beweis f\"ur die Richtigkeit dieser Methoden.