## 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.

### MSC:

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