# $$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.