Submit progress

on Erdős #563 · graph theory / ramsey theory

The statement

Let $F(n,\alpha)$ denote the smallest $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< 1/2$ ,

F(n,\alpha)\sim c_\alpha\log n

for some constant $c_\alpha$ depending only on $\alpha$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.