Logo
All Random Solved Random Open
OPEN
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$.

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.