On Ryser's conjecture for linear intersecting multipartite hypergraphs

DOI10.1016/J.EJC.2016.10.004zbMATH Open1352.05137arXiv1508.00951OpenAlexW1942517911WikidataQ123127683 ScholiaQ123127683MaRDI QIDQ730257FDOQ730257

Authors: Nevena Francetić, Sarada Herke, Ian M. Wanless, Brendan D. McKay 

Publication date: 27 December 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Ryser conjectured that $aule(r-1)u$ for $r$-partite hypergraphs, where $au$ is the covering number and $u$ is the matching number. We prove this conjecture for $rle9$ in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each $r$-partite hypergraph should have a cover of size $(r-1)u$ of a particular form. We provide a counterexample to Aharoni's conjecture with $r=13$ and $u=1$. We also report a number of computational results. For $r=7$, we find that there is no linear intersecting hypergraph that achieves the equality $au=r-1$ in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for $rin9,13,17$. Also, we find that $r=8$ is the smallest value of $r$ for which there exists a linear intersecting $r$-partite hypergraph that achieves $au=r-1$ and is not isomorphic to a subhypergraph of a projective plane.

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

Recommendations

• Multipartite hypergraphs achieving equality in Ryser's conjecture
• A comment on Ryser's conjecture for intersecting hypergraphs
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Nonintersecting Ryser Hypergraphs
• Covers in partitioned intersecting hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Practical graph isomorphism. II.
• A course in combinatorics.
• Ryser's conjecture for tripartite 3-graphs
• Matchings and covers in hypergraphs
• Hall's theorem for hypergraphs
• On Ryser's conjecture
• Title not available (Why is that?)
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture
• A survey of Skolem-type sequences and Rosa’s use of them
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• A family of extremal hypergraphs for Ryser's conjecture
• A note on intersecting hypergraphs with large cover number

Cited In (15)

• Coverings and matchings in \(r\)-partite hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• Ryser's conjecture for \(t\)-intersecting hypergraphs
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• Extremal hypergraphs for Ryser's conjecture
• Intersecting and 2‐intersecting hypergraphs with maximal covering number: The Erdős–Lovász theme revisited
• A family of extremal hypergraphs for Ryser's conjecture
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Title not available (Why is that?)
• On Ryser's conjecture for \(t\)-intersecting and degree-bounded hypergraphs
• A note on intersecting hypergraphs with large cover number
• Nonintersecting Ryser Hypergraphs
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• A comment on Ryser's conjecture for intersecting hypergraphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture

Uses Software

• nauty
• Traces

This page was built for publication: On Ryser's conjecture for linear intersecting multipartite hypergraphs

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