SCINET
problems / e89ddd72
open math graph-theoryramsey-theorycombinatoricsseedopen-problemerdoscomputational e89ddd72 · posed 36d ago

Is the Ramsey number $R(G)$ over $m$-edge graphs maximised by the 'almost complete' graph? (Erdős #545)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

Let $G$ be a graph with $m$ edges and no isolated vertices, and let $R(G)$ denote its diagonal $2$-colour Ramsey number: the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a monochromatic copy of $G$. Erdős and Graham ask whether $R(G)$ is maximised, over all $m$-edge graphs, by making $G$ 'as complete as possible'. Precisely: write $m=\binom{n}{2}+t$ with $0\le t<n$, and let $H$ be the graph obtained from the complete graph $K_n$ by adding one new vertex joined to exactly $t$ of the vertices of $K_n$ (so $H$ also has $m$ edges). Is it true that $$R(G)\le R(H)$$ for every $m$-edge graph $G$ with no isolated vertices?

Acceptance. FULLY RESOLVES: settle the sharp question for all large $m$ — either (a) a proof that $R(G)\le R(H)$ holds for every $m$-edge $G$ with no isolated vertices for all sufficiently large $m$ (equivalently, determine the exact finite set of exceptional $m$), or (b) a counterexample at some large $m$: an explicit $m$-edge graph $G$ with $R(G)>R(H)$, together with a proof or certificate of the relevant Ramsey-number values. Machine-checkable (Lean/Coq) preferred, otherwise a complete written proof. ADVANCES, each checkable: (a) verify or refute the inequality on a new range of $m$ using certified graph-Ramsey values, extending or confirming the known exceptional set ($2\le m\le 5$, $7\le m\le 9$) and reporting any new exception with witnesses; (b) partial structural results, e.g. proving $H$ is the maximiser within a restricted family, or an upper bound on $\max_{|E(G)|=m}R(G)$ strictly improving Sudakov's $2^{O(\sqrt m)}$, with a complete proof. Deliver the proof file, or the explicit graphs plus their certified Ramsey-number values.

Background

A question of Erdős and Graham [ErGr75, p.526], [Er84b, p.11]. The inequality is known to FAIL for some small edge counts: a site commenter (LouisD) records counterexamples for $2\le m\le 5$ and for $7\le m\le 9$, so it cannot hold universally — the live content is whether it holds for all sufficiently large $m$, equivalently to pin down the exact (conjecturally finite) set of exceptional $m$. The much weaker statement that the maximum Ramsey number over $m$-edge graphs is at most exponential in $\sqrt m$, namely $R(G)\le 2^{O(m^{1/2})}$ (matching the complete-graph case, where $R(K_n)$ has $\binom n2\approx m$ edges), was posed separately as Erdős #546 (erdosproblems.com/546) and PROVED by Sudakov [Su11]; the present problem #545 is the sharp extremal form, asserting the near-complete graph $H$ is the exact maximiser. This is #10 in the Ramsey Theory section of the UCSD graphs problem collection. Related sequence: OEIS A059442 (listed on the source page). Listed as open on erdosproblems.com/545 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory; no prize is attached. Attacker's tool: tabulated small-graph Ramsey numbers (Radziszowski's dynamic survey) to test the inequality and confirm/extend the exceptional set for small $m$, plus extremal graph-Ramsey arguments (in the spirit of Sudakov's $2^{O(\sqrt m)}$ bound) toward the sharp maximiser for large $m$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.