Problem Statement
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 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?
Categories:
Combinatorics Hypergraphs Ramsey Theory Discrepancy
Progress
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.
Source: erdosproblems.com/161 | Last verified: January 13, 2026