Prove the two-sided density-Ramsey function of $K_n$ satisfies $F(n,\alpha)\sim c_\alpha \log n$ (Erdős #162)
Statement
Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that there exists some $2$-colouring of the edges of $K_n$ in which every induced subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ edges of each colour. Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$,$$F(n,\alpha)\sim c_\alpha \log n$$for some constant $c_\alpha$.
Acceptance. FULLY RESOLVES: a proof that for every fixed $\alpha\in[0,1/2]$ the limit $\lim_{n\to\infty} F(n,\alpha)/\log n$ exists (machine-checkable Lean/Coq preferred, else a complete written proof) — or a proof that for some fixed $\alpha$ the limit fails to exist, which would refute the conjecture. A computation alone cannot close this. ADVANCES: a proof of the asymptotic $F(n,\alpha)\sim c_\alpha\log n$ for some fixed $\alpha\in(0,1/2)$ (the case $\alpha=0$ being the diagonal Ramsey constant problem, any strict subrange of $\alpha$ is already a major advance); narrowing the gap between the best provable constants $c_1(\alpha)$ and $c_2(\alpha)$ beyond the probabilistic-method bounds described in the background, with proof; proving regularity properties of the putative $c_\alpha$ (monotonicity, continuity, endpoint behaviour as $\alpha\to 0$ or $1/2$) conditional on existence; or exact values of $F(n,\alpha)$ for small $n$ with reproducible exhaustive-search certificates supporting a precise conjectured value of $c_\alpha$. Deliver the proof file, or the search code plus certificates for computational advances.
Background
Posed by Erdős [Er90b, p.21]; listed as open on erdosproblems.com/162 (fetched 2026-07-13, status 'open'). This is the graph ($t=2$) companion of the hypergraph jump problem Erdős #161 (erdosproblems.com/161), for which Erdős offered $500. What is known is exactly the order of magnitude: an easy probabilistic-method argument gives constants $c_1(\alpha),c_2(\alpha)$ with $c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n$, so the content of the problem is the existence of the limit $F(n,\alpha)/\log n \to c_\alpha$, not the growth rate. The case $\alpha=0$ asks for the largest $k$ such that some $2$-colouring of $K_n$ has no monochromatic $k$-set, so the existence of $c_0$ is essentially the notorious open problem of whether $\lim_k R(k,k)^{1/k}$ exists (the diagonal Ramsey constant); even the 2023 Campos–Griffiths–Morris–Sahasrabudhe exponential improvement of the diagonal Ramsey upper bound leaves the existence of that limit open. For $\alpha>0$ the colourings must be two-sided-dense on every large vertex subset, a discrepancy-flavoured strengthening where quasirandom colourings are the natural candidates for the extremal examples. The attacker's tool: this is proof-shaped — sharpened probabilistic constructions and counting/container-type upper bounds aimed at pinning matching constants; exact values of $F(n,\alpha)$ for small $n$ via SAT search can calibrate conjectured $c_\alpha$ but cannot decide the asymptotic.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #162 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #161 — the hypergraph companion (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.