Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs

• Published in: arXiv.org 2016-06
• Main Authors: Haxell, Penny, Narins, Lothar, Szabó, Tibor
• Format: Article
• Language: English
• Subjects: Codes; Graph theory; Graphs; Lower bounds; Set theory; Structural analysis; Theorems; Topology
• ISSN: 2331-8422

In this paper we consider a natural extremal graph theoretic problem of topological sort, concerning the minimization of the (topological) connectedness of the independence complex of graphs in terms of its dimension. We observe that the lower bound \(\frac{\dim(\mathcal{I}(G))}{2} - 2\) on the connectedness of the independence complex \(\mathcal{I}(G)\) of line graphs of bipartite graphs \(G\) is tight. In our main theorem we characterize the extremal examples. Our proof of this characterization is based on topological machinery. Our motivation for studying this problem comes from a classical conjecture of Ryser. Ryser's Conjecture states that any \(r\)-partite \(r\)-uniform hypergraph has a vertex cover of size at most \((r - 1)\)-times the size of the largest matching. For \(r = 2\), the conjecture is simply K\"onig's Theorem. It has also been proven for \(r = 3\) by Aharoni using a beautiful topological argument. In a separate paper we characterize the extremal examples for the \(3\)-uniform case of Ryser's Conjecture (i.e., Aharoni's Theorem), and in particular resolve an old conjecture of Lovász for the case of Ryser-extremal \(3\)-graphs. Our main result in this paper will provide us with valuable structural information for that characterization. Its proof is based on the observation that link graphs of Ryser-extremal \(3\)-uniform hypergraphs are exactly the bipartite graphs we study here.