Problem Statement
Let $F(n,\alpha)$ denote the largest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lvert X\rvert}{2}$ many edges of each colour.
Prove that, for every $0\leq \alpha\leq 1/2$,\[F(n,\alpha)\sim c_\alpha\log n\]for some constant $c_\alpha$ depending only on $\alpha$.
Prove that, for every $0\leq \alpha\leq 1/2$,\[F(n,\alpha)\sim c_\alpha\log n\]for some constant $c_\alpha$ depending only on $\alpha$.
Categories:
Graph Theory Ramsey Theory Hypergraphs
Progress
It is easy to show that, for every $0\leq \alpha\leq 1/2$,\[F(n,\alpha)\asymp_\alpha \log n.\]Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.See also [161].
See also the entry in the graphs problem collection.
Source: erdosproblems.com/563 | Last verified: January 15, 2026