Dual View Random Solved Random Open
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?
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
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

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None

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