Multipartite hypergraphs achieving equality in Ryser's conjecture

DOI10.1007/S00373-015-1575-9MaRDI QIDQ5964971zbMATH OpenOpenAlexWikidataFDO

Authors Ron Aharoni, János Barát, Ian M. Wanless

Publication date 2 March 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4833, http://real.mtak.hu/46091/1/ron_jan_ian.pdf

zbMATH Keywords

covering numberfractional coverintersecting hypergraphRyser's conjecture

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A famous conjecture of Ryser is that in an $r$-partite hypergraph the covering number is at most $r-1$ times the matching number. If true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$. We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $r=7$. For $rin6,7$, we find the minimal number $f(r)$ of edges in an intersecting $r$-partite hypergraph that has covering number at least $r-1$. We find that $f(r)$ is achieved only by linear hypergraphs for $rle5$, but that this is not the case for $rin6,7$. We also improve the general lower bound on $f(r)$, showing that $f(r)ge3.052r+O(1)$. We show that a stronger form of Ryser's conjecture that was used to prove the $r=3$ case fails for all $r>3$. We also prove a fractional version of the following stronger form of Ryser's conjecture: in an $r$-partite hypergraph there exists a set $S$ of size at most $r-1$, contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.

Recommendations

• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• On Ryser's conjecture
• Coverings and matchings in r-partite hypergraphs
• A comment on Ryser's conjecture for intersecting hypergraphs

Cites work

• A comment on Ryser's conjecture for intersecting hypergraphs
• Eigenvalues and homology of flag complexes and vector representations of graphs
• Extremal hypergraphs for Ryser's conjecture
• Hall's theorem for hypergraphs
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Maximum degree and fractional matchings in uniform hypergraphs
• On a generalization of the Ryser-Brualdi-Stein conjecture
• On a Problem of Erdos and Lovasz. II: n(r) = O(r)
• On Ryser's conjecture
• Ryser's conjecture for tripartite 3-graphs
• The clique complex and hypergraph matching
• The intersection of a matroid and a simplicial complex
• Vector representation of graph domination

Cited in

(18)

• A note on a conjecture of Ryser
• 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
• Generalizations and strengthenings of Ryser's conjecture
• A note on intersecting hypergraphs with large cover number
• A note on the edge cover number and independence number in hypergraphs
• Coverings and matchings in r-partite hypergraphs
• On Ryser's conjecture
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Fair representation by independent sets
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
• Covers in partitioned intersecting hypergraphs
• Nonintersecting Ryser Hypergraphs
• A counterexample to Stein's equi-\(n\)-square conjecture
• Intersecting and 2‐intersecting hypergraphs with maximal covering number: The Erdős–Lovász theme revisited
• Extremal hypergraphs for Ryser's conjecture
• On Ryser's conjecture for linear intersecting multipartite hypergraphs

This page was built for publication: Multipartite hypergraphs achieving equality in Ryser's conjecture

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