Characterize hypergraphs with maximum/minimum product of point and line covering numbers

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\).

A problem on the product of the point and line covering numbers (proposed by Chung, Erdös and Graham [1])

In a hypergraph \(G\) with vertex set \(V\) and edge set \(E\), the point covering number \(\alpha_0(G)\) denotes the minimal cardinality of a subset of \(V\) which has non-empty intersection with every edge \(e\) in \(E\). The line covering number \(\alpha_1(G)\) denotes the minimal cardinality of a subset \(S\) of \(E\) such that every vertex is contained in some edge in \(S\). The problem of interest is to characterize hypergraphs which achieve the maximum and minimum value of the product \(\alpha_0(G) \alpha_1(G)\).

The case for graphs was solved in [1], and it was shown that

\(\displaystyle n-1 \leq \alpha_0(G) \alpha_1(G) \leq (n-1) \left\lfloor \frac{n+1}{2}\right\rfloor \)

where each bound is asymptotically best possible.

Bibliography
1 F. R. K. Chung, P. Erdös and R. L. Graham, On the product of the point and line covering numbers of a graph, Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. N. Y. Acad. Sci. 319, 597-602, New York Acad. Sci., New York, 1979.