2025/05/08 by Clow, Alexander, Haxell, Penny, Mohar, Bojan · 2 citations
#05C65 #05C69 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.05339
In 1975 Lovász conjectured that every r-partite, r-uniform hypergraph contains r-1 vertices whose deletion reduces the matching number. If true, this statement would imply a well-known conjecture of Ryser from 1971, which states that every r-partite, r-uniform hypergraph has a vertex cover of size at most r-1 times its matching number. When r=2, Ryser's conjecture is simply Kőnig's theorem, and the conjecture of Lovász is an immediate corollary. Ryser's conjecture for r=3 was proven by Aharoni in 2001, and remains open for all r≥ 4. Here we show that the conjecture of Lovász is false in the case r=3. Our counterexample is the line hypergraph of the Biggs-Smith graph, a highly symmetric cubic graph on 102 vertices.