Sharp $c_\alpha\log n$ asymptotic for the two-colour density-$\alpha$ subgraph threshold (Erdős #563)
Statement
For $0\leq\alpha<1/2$, let $F(n,\alpha)$ be the smallest $m$ such that there exists a $2$-colouring of the edges of the complete graph $K_n$ in which every vertex subset $X\subseteq[n]$ with $\lvert X\rvert\geq m$ spans more than $\alpha\binom{\lvert X\rvert}{2}$ edges of each colour. Prove that, for every fixed $0\leq\alpha<1/2$, $$F(n,\alpha)\sim c_\alpha\log n$$ for some constant $c_\alpha>0$ depending only on $\alpha$.
Acceptance. FULLY RESOLVES: a complete proof that $F(n,\alpha)\sim c_\alpha\log n$ (i.e. the limit $F(n,\alpha)/\log n$ exists) for every fixed $0\leq\alpha<1/2$, together with a description of $c_\alpha$ — machine-checkable (Lean/Coq) preferred, otherwise a full written proof. ADVANCES (each independently checkable): (a) prove the sharp asymptotic for a specific $\alpha\in(0,1/2)$ (note $\alpha=0$ is Ramsey-hard); (b) improve the constants in the known $F(n,\alpha)\asymp_\alpha\log n$ bounds — bring the leading constants of the upper and lower bounds strictly closer than any pair stated in the background, with proof; or (c) determine exact values of $F(n,\alpha)$ for new small $n$ and a fixed $\alpha$ via verified search, with the code and a certificate of optimality. Deliver the proof, the improved constant bounds with proof, or the search code plus exact values.
Background
A problem of Erdős [Er90b, p.21]; listed as open on erdosproblems.com/563 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory | hypergraphs'). When $\alpha=0$ the requirement is that every $X$ with $\lvert X\rvert\geq m$ contains at least one edge of each colour, i.e. there is no monochromatic clique of size $m$; thus $F(n,0)$ is essentially the diagonal Ramsey threshold and the $\alpha=0$ case recovers the classical Ramsey numbers. It is straightforward, via the probabilistic method (a random $2$-colouring together with an alteration/union-bound argument), to show that $F(n,\alpha)\asymp_\alpha\log n$ for every $0\leq\alpha<1/2$ — order $\log n$ with constants depending on $\alpha$. What is open is the sharp asymptotic: that $F(n,\alpha)/\log n$ converges to a constant $c_\alpha$. Even the endpoint $\alpha=0$ is Ramsey-hard — pinning $c_0$ is equivalent to determining $\lim (\log R(n))/n$ for diagonal Ramsey numbers, a famous unresolved question. A hypergraph generalization is Erdős #161 (erdosproblems.com/161); this problem is #39 in the Ramsey Theory section of the collection. No Erdős prize is attached. Attacker's tool: sharpen the probabilistic lower bound (random colourings refined by second-moment or Lovász-local-lemma arguments) against a counting upper bound, and compute $F(n,\alpha)$ exactly for small $n$ by exhaustive / SAT search over $2$-colourings to estimate $c_\alpha$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #563 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.