[#P3136] Ryser’s conjecture for multipartite hypergraphs

Five vertex classes joined by colored hyperedges, with selected vertices forming a transversal. — A structural graph diagram of the statement's mathematical objects.

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?

1Context

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.

2Problem setup

Definition 1 (r-partite, r-uniform hypergraph). The vertex set is partitioned into r classes, and every hyperedge contains exactly one vertex from each class.

Definition 2 (matching number). ν(H) is the largest number of pairwise vertex-disjoint hyperedges.

Definition 3 (transversal number). τ(H) is the smallest number of vertices in a set that meets every hyperedge.

Remark 1. 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.

3What 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).

1Status

Current status (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.^{[1][2][3][4][5]}

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 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][2][3][4][5]} Relevance to this problem This is the dated publication status for the canonical target Ryser’s conjecture for multipartite hypergraphs. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4, Reference 5 Details 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). Open full record →
	Result	Supported
claim · Claim 2 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][2][3][4][5]} Relevance to this problem Locates the present research frontier immediately below Ryser’s conjecture for multipartite hypergraphs. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4, Reference 5 Details 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. This leaves the following boundary unresolved: 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 distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 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][2][3][4][5]} Relevance to this problem Documents why Ryser’s conjecture for multipartite hypergraphs was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4, Reference 5 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - 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 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. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 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. Relevance to this problem Turns the remaining uncertainty in Ryser’s conjecture for multipartite hypergraphs into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: 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 claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - 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). Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

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.

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.

How the 4 records connectTyped relations and evidence flow

ProblemRyser’s conjecture for multipartite hypergraphs

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Cycle Double Cover Conjecturecombinatorics
The Total Coloring Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

How to cite

TheoremDB contributors, “Ryser’s conjecture for multipartite hypergraphs,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/ryser-hypergraph-cover-conjecture

This page as plain text: ryser-hypergraph-cover-conjecture.md

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1References

Packet source. 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. ↗ open copy ↗preprint · primary source · arXiv:2505.05339, checked 2026-08-01 · checked 2026-08-01Source 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.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.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.
Ron Aharoni, “Ryser's Conjecture for Tripartite 3-Graphs”. Combinatorica 21(1) (2001), 1-4. DOI 10.1007/s004930170001. Main theorem. ↗journal article · primary source · checked 2026-08-01Source 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.
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. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source 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.
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. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source 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.
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. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source 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.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3136] Ryser’s conjecture for multipartite hypergraphs

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance