Solution of two fractional packing problems of Lovász. (Reprint) (Q2497997)

This is a reprint of an important article published in Discrete Math. 26, 177--184 (1979; Zbl 0413.05044). Let \(H\) be a hypergraph. Denote its \(k\)-matching number by \(\nu_k(H)\), its \(k\)-covering number by \(\tau_k(H)\). Denote the fractional matching and covering numbers by \(\nu^*(H)\) and \(\tau^*(H)\), respectively. It is shown that, if \(k \nu^*(H')\) is an integer for each hypergraph \(H'\) arising from \(H\) by multiplying vertices, then \(k \nu^*(H) = \tau_k(H)\) holds. A consequence is the following: If \(\nu_k(H') = k \nu^*(H')\) holds for each hypergraph \(H'\) arising from \(H\) by multiplying vertices, then \(\nu_k(H) = \tau_k(H)\). The dual statement, however, is shown to be false. There is a hypergraph \(H\) such that \(\tau_k(H') = k \tau^*(H')\) holds for each hypergraph \(H'\) arising from \(H\) by removing edges, but \(\nu_k(H) \neq \tau_k(H)\).