Conjecture on covering a hypergraph

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 conjecture on covering a hypergraph (proposed by Erdös and Lovász [2])

Let \(f(n)\) denote the smallest integer \(m\) such that for any \(n\)-element sets \(A_1, \dots, A_m\) with \(A_i \cap A_j \neq \emptyset\) for \(i \neq j\), and for every set \(S\) with at most \(n-1\) elements, there is an \(A_i\) disjoint from \(S\). Determine \(f(n)\).

By considering the lines of a finite geometry, the following upper bound can be easily obtained:

\(\displaystyle f(n) \leq n^2-n+1. \)

Erdös and Lovász [2] proved that

\(\displaystyle \frac 8 3 n -3 \leq f(n) \leq c n^{3/2} \log n. \)

Kahn [3] showed that \( f(n) = O(n)\). For the lower bound for \( f(n)\), Dow et al [1] proved that \( f(n) > 3n\) for \( n \geq 4\).


Bibliography
1 S. J. Dow, D. A. Drake, Z. Füredi and J. A. Larson. A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size. Proceedings of the sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 48 (1985), 47-48.

2 P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 609-627, North-Holland, Amsterdam, 1975.

3 J. Kahn, On a problem of Erdös and Lovász: random lines in a projective plane, Combinatorica 12 (1992), 417-423.