Bounding the vertex cover number of a hypergraph
For a hypergraph \(H\), let \(\tau (H)\) be the minimum \(k\) such that some set of \(k\) vertices meets all the edges and let \(\nu (H)\) be the maximum \(k\) such that some \(k\) edges are pairwise disjoint. Let \(\lambda (H)\) be the maximum \(k \geq 2\) such that the incidence matrix of \(H\) has as a submatrix the transpose of the incidence matrix of the complete graph \(K_ k\). This paper shows that \(\tau (H)\) is bounded above by a function of \(\nu (H)\) and \(\lambda (H)\), and indeed that if \(\lambda (H)\) is bounded by a constant then \(\tau (H)\) is at most a polynomial function of \(\nu (H)\).
scientific article; zbMATH DE number 567470