Matching number drop by k(r−1) deletions

AX_r_partite_hypergraph_matching_drop_deletion

Source: arXiv:2505.05339 — A Counterexample to a Conjecture of Lovász

Conjecture 4.3 · arXiv:2505.05339

arXiv Conjecture high confidence— first stated 2025-06-10

Authors: Alexander Clow, Penny Haxell, Bojan Mohar

Status ai-disproved high confidence

Disproved by OpenAI's counterexamples to Ryser's conjecture, which this statement implies.

Cited literature (1)

partial Infinitely many counterexamples to a conjecture of Lovász (2025)

Aida Abiad, Frederik Garbe, Xavier Povill, Christoph Spiegel · arXiv preprint · arXiv:2506.21286

In the concluding remarks (Section 5), the authors mention the conjecture explicitly, report computational verification that it holds for smaller r=3 counterexamples to Lovász's conjecture, but conclude that checking larger graphs or r=4 counterexamples is computationally infeasible and that their theoretical tools are insufficient to settle the question.

Reviewer notes. Literature status before this model-generated claim: open. Conjecture 4.3 from arXiv:2505.05339, proposed as a weakening of Lovász's (now disproved) conjecture that still implies Ryser's conjecture, remains open as of 2026. The subsequent paper arXiv:2506.21286 (Abiad, Garbe, Povill, Spiegel, 2025) explicitly discusses it in its concluding remarks, reporting computational verification for some smaller r=3 counterexamples to Lovász's conjecture, but acknowledging that larger cases are computationally infeasible and that the conjecture cannot be resolved by their theoretical methods.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Why it applies. The manuscripts' hypergraphs are intersecting ($\nu = 1$), $r$-partite and $r$-uniform with covering number $r$. With $\nu = 1$ the statement forces $k = 1$: $r-1$ vertices whose deletion leaves no edge, i.e. a vertex cover of size $r-1$, which does not exist.

A counterexample to Ryser's covering conjecture — main result formalized in Lean by OpenAI
Balanced counterexamples to Ryser's conjecture at prime orders — main result formalized in Lean by OpenAI

Family 162: Counterexamples to Ryser’s covering conjecture · Lean formalization scope

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry open. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. For every $r$-partite $r$-uniform hypergraph $\mathcal{H}$ there exists some $k$ with $1\leq k\leq r-1$ such that $\mathcal{H}$ contains $k(r-1)$ vertices whose deletion reduces the matching number by at least $k$.

Context

Proposed as a weakening of Lovász's (now disproved) conjecture that still implies Ryser's conjecture. The authors verified it holds for the line hypergraph of the Biggs-Smith graph, and note that only two counterexamples to Lovász's original conjecture are known, suggesting a slightly weaker statement may be true.

Source paper

A Counterexample to a Conjecture of Lovász
Alexander Clow, Penny Haxell, Bojan Mohar · 2025-06-10
https://arxiv.org/abs/2505.05339