Extremal hypergraphs for Ryser's conjecture

DOI10.1016/J.JCTA.2018.04.004MaRDI QIDQ721059zbMATH OpenOpenAlexWikidataFDO

Authors Lothar Narins, Tibor Szabó, Penny Haxell

Publication date 18 July 2018

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0171

zbMATH Keywords

Ryser's conjectureextremal 3-partite 3-uniform hypergraphhome-base hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: 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 and every bipartite graph is a witness for its tightness. The conjecture has also been proven for $r=3$ by Aharoni using topological methods, but the proof does not give information on the extremal $3$-uniform hypergraphs. Our goal in this paper is to characterize those hypergraphs which are tight for Aharoni's Theorem. Our proof of this characterization is also based on topological machinery, particularly utilizing results on the (topological) connectedness of the independence complex of the line graph of the link graphs of $3$-uniform Ryser-extremal hypergraphs, developed in a separate paper. The current paper contains the second, structural hypergraph-theoretic part of the argument, where we use the information on the line graph of the link graphs to nail down the elements of a structure we call emph{home-base hypergraph}. While there is a single minimal home-base hypergraph with matching number $k$ for every positive integer $kinmathbbN$, home-base hypergraphs with matching number $k$ are far from being unique. There are infinitely many of them and each of them is composed of $k$ copies of two different kinds of basic structures, whose hyperedges can intersect in various restricted, but intricate ways. Our characterization also proves an old and wide open strengthening of Ryser's Conjecture, due to Lov'asz, for the $3$-uniform extremal case, that is, for hypergraphs with $au=2u$.

Recommendations

• A family of extremal hypergraphs for Ryser's conjecture
• Nonintersecting Ryser Hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• On Ryser's conjecture
• Multipartite hypergraphs achieving equality in Ryser's conjecture

Cites work

• scientific article; zbMATH DE number 3884213 (Why is no real title available?)
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A comment on Ryser's conjecture for intersecting hypergraphs
• A note on the edge cover number and independence number in hypergraphs
• Extremal hypergraphs for Ryser's conjecture
• Extremal problems for transversals in graphs with bounded degree
• Hall's theorem for hypergraphs
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Maximum degree and fractional matchings in uniform hypergraphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture
• On Ryser's conjecture
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• Ryser's conjecture for tripartite 3-graphs
• The intersection of a matroid and a simplicial complex
• Triangulated spheres and colored cliques

Cited in

(10)

• Generalizations and strengthenings of Ryser's conjecture
• Ryser's conjecture for \(t\)-intersecting hypergraphs
• On the König-Hall-Egerváry theorem for multidimensional matrices and multipartite hypergraphs
• Extremal hypergraphs for Ryser's conjecture
• Economical extremal hypergraphs for the Erdős-Selfridge theorem
• A family of extremal hypergraphs for Ryser's conjecture
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• A note on intersecting hypergraphs with large cover number
• Nonintersecting Ryser Hypergraphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture

This page was built for publication: Extremal hypergraphs for Ryser's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q721059)