Infinitely many counterexamples to a conjecture of Lovász

2025/06/26 by Aida Abiad, Frederik Garbe, Abiad, Aida +5 · 1 citation
Mathematics · #Analytic and geometric function theory #Combinatorics (math.CO) #FOS: Mathematics #Functional Equations Stability Results #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2506.21286

openalex publication_date 2025/06/26 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

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.

Citations

• A Counterexample to a Conjecture of Lovász
• Edge-transitive cubic graphs: Cataloguing and Enumeration
• The transitive groups of degree 48 and some applications
• Ryser's Conjecture for t-intersecting hypergraphs
• A Census of Small Transitive Groups and Vertex-Transitive Graphs
• A family of extremal hypergraphs for Ryser's conjecture
• Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs
• Practical graph isomorphism, II

Cited by

• Hall's theorem for reconfigurations and higher dimensional topological connectedness

Related

• A Counterexample to a Conjecture of Lovász
• Extremal Hypergraphs for Ryser's Conjecture: Home-Base Hypergraphs
• A family of extremal hypergraphs for Ryser's conjecture
• Matching and intersection problems for non-trivial r-partite r-uniform hypergraphs
• On Positive Matching Decomposition Conjectures of Hypergraphs