OPEN
This is open, and cannot be resolved with a finite computation.
- $500
Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.
For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?
For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Hajnal, and Rado (see
[562]) implies that\[ F^{(t)}(n,0)\asymp \log_{t-1} n\]and results of Erdős and Spencer imply that\[F^{(t)}(n,\alpha) \gg_\alpha (\log n)^{\frac{1}{t-1}}\]for all $\alpha>0$, and a similar upper bound holds for $\alpha$ close to $1/2$.
Erdős believed there might be just one jump, occcurring at $\alpha=0$.
Conlon, Fox, and Sudakov
[CFS11] have proved that, for any fixed $\alpha>0$,\[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\]Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.
For all $\alpha>0$ it is known that\[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\]See also
[563].
See also
the entry in the graphs problem collection.
View the LaTeX source
This page was last edited 18 October 2025.
Additional thanks to: 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 #161, https://www.erdosproblems.com/161, accessed 2026-01-16
