Does chromatic number $k$ force the Ramsey number $R(G)$ close to $R(k)$? (Erdős #87)
Statement
For a graph $G$, let $R(G)$ be its Ramsey number: the least $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $G$; write $R(k)=R(K_k)$ for the diagonal Ramsey number. Fix $\epsilon>0$. Is it true that, for all sufficiently large $k$, every graph $G$ with chromatic number $\chi(G)=k$ satisfies $$R(G)>(1-\epsilon)^k R(k)?$$ Stronger form: is there an absolute constant $c>0$ such that $R(G)>c\,R(k)$ for every graph $G$ with $\chi(G)=k$ and all large $k$?
Acceptance. FULLY RESOLVES: a complete proof settling either form of the question — for instance a proof that for every $\epsilon>0$ and all large $k$, every $k$-chromatic $G$ satisfies $R(G)>(1-\epsilon)^k R(k)$ (and/or the stronger constant-fraction statement); or, disproving it, a construction of $k$-chromatic graphs $G$ for arbitrarily large $k$ with $R(G)\leq(1-\epsilon)^k R(k)$ for some fixed $\epsilon>0$ (or $R(G)<c R(k)$ for every constant $c$), with proof. Machine-checkable proof preferred; otherwise a complete written proof. ADVANCES (each independently checkable): (a) improve Wigderson's lower bound $R(G)\gg 2^{k/2}$ for $k$-chromatic $G$ toward a constant fraction of $R(k)$, with a complete proof; or (b) exhibit a new small $k$-chromatic graph $G$ whose ratio $R(G)/R(k)$ is smaller than any previously recorded — deliver $G$, an explicit $2$-colouring of $K_{R(G)-1}$ with no monochromatic $G$, and a proof (search certificate) that $R(G)$ has the claimed value.
Background
Posed by Erdős [Er95, p.14]; listed as open on erdosproblems.com/87 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'), with no cash prize. Erdős originally conjectured the clean inequality $R(G)\geq R(k)$ for every $k$-chromatic $G$ — trivial for $k=3$ — but this already fails at $k=4$: Faudree–McKay [FaMc93] computed $R(W)=17$ for the pentagonal wheel $W$ (which has $\chi(W)=4$), whereas $R(4)=R(K_4)=18$. Hence the weakened multiplicative forms above. Known facts: since $R(k)\leq 4^k$, the $(1-\epsilon)^k$ inequality is trivial once $\epsilon\geq 3/4$. Yuval Wigderson observed that $R(G)\gg 2^{k/2}$ for every graph $G$ with $\chi(G)=k$ (a random $2$-colouring cannot avoid a monochromatic $k$-chromatic subgraph much before $\sim 2^{k/2}$ vertices), which asymptotically matches the best-known lower bounds for $R(k)$ itself. The open gap is precisely between 'matches the lower bound for $R(k)$' and 'is a constant fraction (or a $(1-\epsilon)^k$ fraction) of $R(k)$'. This is #12/#13 in the Ramsey Theory section of the graphs problem collection, and is closely tied to the diagonal Ramsey growth constant of Erdős #77 (erdosproblems.com/77). Attacker's tool: exact or near-exact Ramsey-number computation for small $k$-chromatic graphs (SAT / clique search, as Faudree–McKay used to get $R(W)=17$) to hunt for $k$-chromatic $G$ with unusually small ratio $R(G)/R(k)$, testing the $(1-\epsilon)^k$ and constant-fraction predictions and possibly exposing counterexamples.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #87 (T. F. Bloom) | website |
| REF-02 | OEIS A059442 — array of Ramsey numbers R(n,k) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.