On Ryser's conjecture for linear intersecting multipartite hypergraphs

DOI10.1016/J.EJC.2016.10.004MaRDI QIDQ730257zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

Hypergraphs (05C65)

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.

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

Cites work

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

Cited in

(15)

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

Describes a project that uses

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)