### 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.052*r*+*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 language | English |
---|---|

Pages (from-to) | 1-15 |

Number of pages | 15 |

Journal | Graphs and Combinatorics |

Volume | 32 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2016 |

### Keywords

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

## Cite this

Aharoni, R., Barat, J., & Wanless, I. M. (2016). Multipartite hypergraphs achieving equality in Ryser's conjecture.

*Graphs and Combinatorics*,*32*(1), 1-15. https://doi.org/10.1007/s00373-015-1575-9