# P3136: Ryser’s conjecture for multipartite hypergraphs

- ID: `P3136`
- Reference: `ryser-hypergraph-cover-conjecture`
- Page: https://theoremdb.org/statements/P3136
- Record maturity: Reviewed problem with recorded work

## Problem

For every integer \(r\ge2\) and every finite \(r\)-partite, \(r\)-uniform hypergraph \(H\), must its transversal number satisfy \(\tau(H)\le(r-1)\nu(H)\), where \(\nu(H)\) is its matching number?

### Context

Known frontier: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families.

Open boundary: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent repository target.

### Problem setup

- **Definition (r-partite, r-uniform hypergraph).** The vertex set is partitioned into r classes, and every hyperedge contains exactly one vertex from each class.
- **Definition (matching number).** ν(H) is the largest number of pairwise vertex-disjoint hyperedges.
- **Definition (transversal number).** τ(H) is the smallest number of vertices in a set that meets every hyperedge.
- **Remark.** Each hyperedge chooses one vertex from each of r vertex classes. A matching is a collection of pairwise disjoint hyperedges. A transversal is a set of vertices meeting every hyperedge. Ryser’s conjecture says a transversal can always be chosen with at most r-1 vertices for each edge in a maximum matching.

### What counts as a solution

- Prove τ(H) ≤ (r-1)ν(H) for every finite r-partite, r-uniform hypergraph and every r≥2.
- Or give an explicit r-partite, r-uniform hypergraph H with a certified matching number and transversal number satisfying τ(H)>(r-1)ν(H).

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families. Exact unresolved remainder: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target. [1](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4) [5](#reference-5)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families. Exact unresolved remainder: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families.

The exact unresolved remainder is: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target.

A complete resolution must meet the following acceptance conditions:
- Prove τ(H) ≤ (r-1)ν(H) for every finite r-partite, r-uniform hypergraph and every r≥2.
- Or give an explicit r-partite, r-uniform hypergraph H with a certified matching number and transversal number satisfying τ(H)>(r-1)ν(H).

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families. Exact unresolved remainder: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target.
- The release review checked 5 structured sources on 2026-08-01.
- Equivalent-formulation queries: Ryser conjecture r-partite hypergraph open 2026; Ryser conjecture remains open for all r greater than or equal to 4; Ryser conjecture intersecting hypergraph r 6 open; Lovasz conjecture counterexample Ryser 2025
- Strongest checked neighboring result: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families.
- Exact unresolved remainder: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target.

### Other known results

- **Claim 2** (supported): The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families. [1](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4) [5](#reference-5)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The conjecture is proved for all hypergraphs when r≤3 and for intersecting hypergraphs when r≤5. For r=4 and r=5, Haxell and Scott prove τ(H)≤(r-ε)ν(H) for some ε>0. Further exact cases include maximum degree at most 2 and several strongly intersecting families. Unresolved remainder: Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target. [1](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4) [5](#reference-5)

### Open directions

- **Route 2** (reported): Prove the conjectured coefficient r-1 for arbitrary r-partite, r-uniform hypergraphs when r≥4, or give a counterexample. Even the intersecting case ν(H)=1 remains open for every r≥6. The 2025 counterexample to the stronger Lovász conjecture does not settle Ryser’s conjecture. Corpus searches found only unrelated Bruck-Ryser references and no equivalent TheoremDB target.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `ryser-hypergraph-cover-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Clow, Alexander, Haxell, Penny, and Mohar, Bojan, “A Counterexample to a Conjecture of Lovász”. arXiv (2025). DOI 10.48550/arXiv.2505.05339. Abstract and Introduction https://doi.org/10.48550/arXiv.2505.05339
   - Also cited at A. Clow, P. Haxell, and B. Mohar, A Counterexample to a Conjecture of Lovász, arXiv:2505.05339 (2025). Abstract and Introduction
   - preprint; primary source; arXiv:2505.05339, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2505.05339
   - Source use: original_summary
   - States that Ryser’s conjecture remains open for every r≥4 and disproves a stronger Lovász conjecture that would have implied it.
   - Source used to assess the problem's recorded status.
   - For Ryser’s conjecture for multipartite hypergraphs: This is the dated publication status for the canonical target Ryser’s conjecture for multipartite hypergraphs.
   - Source named by the research packet.
2. <a id="reference-2"></a>Ron Aharoni, “Ryser's Conjecture for Tripartite 3-Graphs”. Combinatorica 21(1) (2001), 1-4. DOI 10.1007/s004930170001. Main theorem https://doi.org/10.1007/s004930170001
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Proves τ(H)≤2ν(H) for tripartite 3-uniform hypergraphs, settling the last universally proved value r=3.
   - Source used to assess the problem's recorded status.
   - For Ryser’s conjecture for multipartite hypergraphs: Proves τ(H)≤2ν(H) for tripartite 3-uniform hypergraphs, settling the last universally proved value r=3.
3. <a id="reference-3"></a>P. E. Haxell and A. D. Scott, “On Ryser's conjecture”. The Electronic Journal of Combinatorics 19(1) (2012), P23. DOI 10.37236/1175. Abstract and main theorem https://doi.org/10.37236/1175
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p23
   - Source use: original_summary
   - Proves that for r=4 and r=5 there is ε>0 such that τ(H)≤(r-ε)ν(H), improving the elementary rν(H) scale without reaching the conjectured coefficient r-1.
   - Source used to assess the problem's recorded status.
   - For Ryser’s conjecture for multipartite hypergraphs: Proves that for r=4 and r=5 there is ε>0 such that τ(H)≤(r-ε)ν(H), improving the elementary rν(H) scale without reaching the conjectured coefficient r-1.
4. <a id="reference-4"></a>Louis DeBiasio, Yigal Kamel, Grace McCourt, and Hannah Sheats, “Generalizations and Strengthenings of Ryser's Conjecture”. The Electronic Journal of Combinatorics 28(4) (2021), P4.37. DOI 10.37236/9914. Abstract and sections on known cases https://doi.org/10.37236/9914
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2009.07239
   - Source use: original_summary
   - Records that the conjecture is known universally only for r≤3, and for intersecting hypergraphs only through r≤5, while developing equivalent and stronger formulations.
   - Source used to assess the problem's recorded status.
   - For Ryser’s conjecture for multipartite hypergraphs: Records that the conjecture is known universally only for r≤3, and for intersecting hypergraphs only through r≤5, while developing equivalent and stronger formulations.
5. <a id="reference-5"></a>Zoltán Király and Lilla Tóthmérész, “On Ryser’s Conjecture for $t$-Intersecting and Degree-Bounded Hypergraphs”. The Electronic Journal of Combinatorics 24(4) (2017), P4.40. DOI 10.37236/6448. Abstract and main theorems https://doi.org/10.37236/6448
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/1705.10024
   - Source use: original_summary
   - Proves the related t-intersecting bound when t>r/4 and proves Ryser’s conjecture for hypergraphs of maximum degree at most 2.
   - Source used to assess the problem's recorded status.
   - For Ryser’s conjecture for multipartite hypergraphs: Proves the related t-intersecting bound when t>r/4 and proves Ryser’s conjecture for hypergraphs of maximum degree at most 2.