\(3\)-chromatic cliques have edges with large intersection

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.

A problem on \(3\)-chromatic \(r\)-cliques ($100) (proposed by Erdös and Lovász [1], [2])

Let \(H\) be an \(r\)-graph in which every two edges have a nontrivial intersection (that is, \(H\) is an \(r\)-clique). Suppose that \(H\) is \(3\)-chromatic. Is it true that \(H\) contains two edges \(E\) and \(F\) for which \[ |E \cap F| \geq r-2 ? \]

Erdösand Lovász [1], [2] proved that there are always two edges \( E\) and \( F\) in such an \( r\)-clique such that

\(\displaystyle \vert E \cap F\vert \geq \frac{r}{\log r}. \)

The lines of the Fano plane give an example for an \( r\)-graph with \( \vert E \cap F\vert = r-2\) (see [2]).

They also showed that in a \( 3\)-chromatic \( r\)-clique there are at least three different values which are the sizes of the pairwise intersection of edges for large enough \( r\).


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 P. Erdös. Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217-227, János Bolyai Math. Soc., Budapest, 1994.