Problem 563

Erdős Problem #563: declared status 'open'. Formalized: no. 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$. Current best: 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. Prize: no. Tags: graph theory, hypergraphs, ramsey theory.