Multipartite hypergraphs achieving equality in Ryser's conjecture

Ron Aharoni, Janos Barat, Ian M Wanless

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

A famous conjecture of Ryser (1967) 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 r ∈ {6, 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 r ≤ 5, but that this is not the case for r ∈ {6, 7}. We also improve the general lower bound on f(r), showing that f(r) ≥ 3.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.
Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalGraphs and Combinatorics
Volume32
Issue number1
DOIs
Publication statusPublished - 2016

Keywords

  • Covering number
  • Fractional cover
  • Intersecting hypergraph
  • Ryser’s conjecture

Cite this