Finding small global vertex covers for r-graphs with small local vertex covers

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

Problem (proposed by Erdös, Fon der Flaass, Kostochka and Tuza [2])

Determine the smallest integer \(f_r(k,s)\) such that if in an \(r\)-graph \(H\), there is a set \(S\) of size \(s\) intersecting each of the \(k\) edges, for any choice of \(k\) edges, then there is a set of size at most \(f_r(k,s)\) intersecting every edge of \(H\).

In [2], it was shown that
\begin{eqnarray*} f_r(3,2)&=& 2r
f_r(4,2)&=& \left\lceil \frac{3r}{2} \right\rceil
f_r(5,2)&=& \left\lceil \frac{5r}{4} \right\rceil
f_r(6,2)&=& r. \end{eqnarray*}

Erdös [1] stated that the proof of \( f_r(6,2)\) is quite tricky for \( r\) odd, and he conjectured:

\(\displaystyle f_r(7,2) = (1+o(1)) \frac{3r}{4} \)

\(\displaystyle f_r(7,2) = (1+o(1)) c_r r. \)

Most of the cases remain untouched, especially for \( s >2\).

Bibliography
1 P. Erdös. Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81-85.

2 P. Erdös, D. Fon Der Flaass, A. Kostochka and Z. Tuza. Small transversals in uniform hypergraphs, Siberian Advances in Mathematics, Siberian Adv. Math. 2 (1992) no. 1, 82-88.