Maximum vertices in a \(3\)-chromatic \(r\)-clique

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 hypergraph \( H\) is said to be \( k\)-chromatic if the vertices of \( H\) can be colored in \( k\) colors so that every edge has at least \( 2\) colors.

An \( r\)-graph is said to be a clique if every two edges have a nontrivial intersection. An unexpected fact about \( 3\)-chromatic \( r\)-graphs is that there are only finitely many \( 3\)-chromatic \( r\)-cliques.

A problem on maximum \(3\)-chromatic hypergraphs (proposed by Erdös and Lovász [1])

Determine the maximum number \(N(r)\) of vertices a \(3\)-chromatic \(r\)-clique can have.

In [1], it was shown that

\(\displaystyle \frac 1 2 \binom{2r-2}{r-1}+ 2r-2 \leq N(r) \leq \frac {r}{ 2} \binom{2r-1}{r-1}. \)

Tuza [2] proved that

\(\displaystyle 2 \binom{2r-4}{r-2}+ 2r-4 \leq N(r) \leq \binom{2r-2}{r-1}+\binom{2r-4}{r-2}. \)

Bibliography
1 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.

2 Zs. Tuza. Critical hypergraphs and intersecting set-pair systems. J. Comb. Theory B 39 (1985), 134-145.