An application of set-pair systems for multitransversals. (English) Zbl 0749.05048

Let a hypergraph \(H\) with the vertex set \(X\) be given. For a positive integer \(k\) a subset \(Y\) of \(X\) is called a \(k\)-transversal set of \(H\), if the intersection of \(Y\) with each edge of \(H\) has at least \(k\) vertices. The \(k\)-transversal number \(\tau_ k(H)\) of \(H\) is the minimum number of vertices of a \(k\)-transversal set in \(H\). It is proved that for every positive integer \(k\) the problem of determining the \(k\)-transversal number of \((k+1)\)-uniform hypergraphs is \(NP\)-complete. A \(k\)-transversal critical hypergraph is a hypergraph \(H\) whose \(k\)-transversal number decreases after deleting an arbitrary edge. An upper bound for its number of vertices is found in terms of \(k\), of the number of vertices and of the \(k\)-transversal number; furthermore a theorem related to the above one is proved.


05C65 Hypergraphs
05C35 Extremal problems in graph theory
Full Text: EuDML