This work finds infinite counterexamples to Lovász's conjecture about matchings and vertex covers in hypergraphs, suggesting limitations in existing theories.
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$.
No takes yet. Share an insight, caveat, or question.
Abiad et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: