[#P3136] Ryser’s conjecture for multipartite hypergraphs

Contents

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?

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

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · August 1, 2026

What counts as a solution

Saved packet 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]}

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemRyser’s conjecture for multipartite hypergraphs

All 3 recorded relations between these records and the problem

2See also

Constructing a union from non-cancelling intersectionscombinatorics
Plane tilings by every five-cell lattice animalcombinatorics
Cycle Double Cover Conjecturecombinatorics

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Ryser’s conjecture for multipartite hypergraphs.” TheoremDB. P3136. Problem statement; statement text SHA-256 f96dd02f4aed7fbeed25cd870dadf388557c2f8cf8f925aa6e7596de6e55f2dc. https://theoremdb.org/statement/?ref=P3136

BibTeX

@misc{theoremdb-problem-f96dd02f4aed7fbeed25cd870dadf388557c2f8cf8f925aa6e7596de6e55f2dc,
  title = {{Ryser’s conjecture for multipartite hypergraphs}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 f96dd02f4aed7fbeed25cd870dadf388557c2f8cf8f925aa6e7596de6e55f2dc},
  url = {https://theoremdb.org/statement/?ref=P3136}
}

Plain text: Built Markdown snapshot

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.

Discussion

Loading discussion.

[#P3136] Ryser’s conjecture for multipartite hypergraphs

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance