Infinitely Many Counterexamples to a Conjecture of Lovász

The matching number \(\nu(G)\) of a graph \(G\) is the maximum number of pairwise disjoint edges. The vertex cover number \(\tau(G)\) is the minimum cardinality of a set of vertices which intersects every edge. It is a classical result in graph theory, called König’s theorem, that \(\tau(G)=\nu(G)\) for every bipartite graph \(G\). For \(r\)-partite \(r\)-uniform hypergraphs it was conjectured by Ryser that \(\tau(G)\leq (r-1)\nu(G)\). Moreover, Lovász conjectured in 1975 that one can always reduce the matching number by removing \(r-1\) vertices which would imply Ryser’s conjecture. Clow, Haxell, and Mohar very recently disproved this for \(r=3\) using the explicit counterexample of a line hypergraph of a \(3\)-regular graph of order \(102\). We construct the first infinite family of counterexamples for \(r=3\), the smallest of which is the line hypergraph of a graph of order only \(22\). In addition, we give the first counterexamples for \(r=4\).

This is joint work with Aida Abiad, Xavier Povill, and Christoph Spiegel.