PROVED
This has been solved in the affirmative.
Does there exist an absolute constant $c>0$ such that, for all $r\geq 2$, in any $r$-uniform hypergraph with chromatic number $3$ there is a vertex contained in at least $(1+c)^r$ many edges?
In general, determine the largest integer $f(r)$ such that every $r$-uniform hypergraph with chromatic number $3$ has a vertex contained in at least $f(r)$ many edges. It is easy to see that $f(2)=2$ and $f(3)=3$. Erdős did not know the value of $f(4)$.
This was solved by Erdős and Lovász
[ErLo75], who proved in particular that there is a vertex contained in at least\[\frac{2^{r-1}}{4r}\]many edges.
View the LaTeX source
Additional thanks to: Noga Alon and Zach Hunter
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 #833, https://www.erdosproblems.com/833, accessed 2025-11-16
All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.
