What type of study is this?

October 16, 2025Open Access

Infinitely many counterexamples to a conjecture of Lovász

Key Points

Infinitely many counterexamples exist for Lovász's conjecture on maximum matchings and minimum vertex covers.
Counterexamples for $r=3$ were recently disproven and are based on a specific graph structure.
The findings extend to specific counterexamples when $r=4$, indicating broader implications for hypergraph theories.
These results imply significant limitations in the conjectures regarding matchings in multi-partite hypergraphs.

Abstract

Motivated by the well-known conjecture of Ryser which relates maximum matchings to minimum vertex covers in r-partite r-uniform hypergraphs, Lovász formulated a stronger conjecture. It states that one can always reduce the matching number by removing r-1 vertices. This conjecture was very recently disproven for r=3 by Clow, Haxell, and Mohar using the line graph of a 3-regular graph of order 102. Building on this, we describe a simple infinite family of counterexamples based on generalized Petersen graphs for the case r=3 and give specific counterexamples for r=4.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Abiad et al. (Thu,) studied this question.

synapsesocial.com/papers/68f04acce559138a1a06e80e https://doi.org/https://doi.org/10.48550/arxiv.2506.21286

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark

View Full Paper