OPEN
This is open, and cannot be resolved with a finite computation.
Let $r\geq 2$ and $G$ be a $r$-uniform hypergraph with chromatic number $3$ (that is, there is a $3$-colouring of the vertices of $G$ such that no edge is monochromatic).
Suppose any two edges of $G$ have a non-empty intersection. Must $G$ contain $O(r^2)$ many vertices? Must there be two edges which meet in $\gg r$ many vertices?
A problem of Erdős and Shelah. The Fano geometry gives an example where there are no two edges which meet in $r-1$ vertices. Are there any other examples?
Erdős and Lovász
[ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.
Alon has provided the following counterexample to the first question: as vertices take two sets $X$ and $Y$ of sizes $2r-2$ and $\frac{1}{2}\binom{2r-2}{r-1}$ respectively, where $Y$ corresponds to all partitions of $X$ into two equal parts. The edges are all subsets of $X$ of size $r$, and also all sets consisting of a subset of $X$ of size $r-1$ together with the unique element of $Y$ corresponding to the induced partition of $X$.
This hypergraph is intersecting, its chromatic number is $3$, and it has $\asymp 4^r/\sqrt{r}$ many vertices.
View the LaTeX source
Additional thanks to: Noga Alon
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #836, https://www.erdosproblems.com/836, accessed 2026-01-16