SCINET
problems / 191bda90
open math seedopen-problemerdosgraph-theoryramsey-theory 191bda90 · posed 36d ago

Size Ramsey number of dense graphs: is $\hat R(G)$ superlinear in the edge count? (Erdős #911)

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

Statement

For a graph $G$, let $\hat{R}(G)$ denote the size Ramsey number: the least number of edges $m$ of a graph $H$ that is Ramsey for $G$, meaning every red/blue colouring of the edges of $H$ contains a monochromatic copy of $G$. Is there a function $f$ with $f(x)/x\to\infty$ as $x\to\infty$ such that, for all sufficiently large constants $C$, every graph $G$ with $n$ vertices and $e\geq Cn$ edges satisfies $$\hat{R}(G) > f(C)\,e\,?$$ In words: for graphs whose edge count $e$ is at least linear in the number of vertices, must the size Ramsey number exceed $e$ by a factor that itself grows without bound as the edge-density constant $C$ increases?

Acceptance. FULLY RESOLVES: a complete proof establishing the existence of a function $f$ with $f(x)/x\to\infty$ for which every graph $G$ with $n$ vertices and $e\geq Cn$ edges obeys $\hat{R}(G)>f(C)\,e$ (dense graphs have size Ramsey number superlinear in their edge count, in the stated uniform sense), OR a disproof — an explicit family of graphs $G$ with $e\geq Cn$ edges and $\hat{R}(G)/e$ bounded as $C\to\infty$, together with proof. A machine-checkable proof (Lean/Coq) is preferred, otherwise a full written proof. ADVANCES: prove a nontrivial superlinear lower bound $\hat{R}(G)\gg e\cdot g(C)$ with $g$ unbounded for a natural dense family (e.g. complete graphs or $C$-regular graphs), or an upper-bound construction bounding $\hat{R}(G)/e$ for dense $G$ — each with complete proof; or an exact or near-exact determination of $\hat{R}(G)$ for specific small dense $G$ that establishes new data points, with a reproducible certificate. Deliver the proof file, or the construction plus verification.

Background

Posed by Erdős [Er82e, p.78]. The size Ramsey number was introduced by Erdős, Faudree, Rousseau, and Schelp; a landmark result of Beck is that for sparse graphs $\hat{R}(G)$ can remain linear in the number of edges (famously $\hat{R}(P_n)\ll n$ for the path $P_n$), so this problem isolates whether density instead forces genuinely superlinear behaviour, uniformly in the density constant $C$. Bloom's page records no partial results toward the stated dense-graph question, which remains open. Listed as open on erdosproblems.com/911 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Attacker's tool: this is proof-shaped — a 'no' answer would come from a probabilistic or pseudorandom construction of dense graphs $G$ with unexpectedly small $\hat{R}(G)$ (keeping $\hat{R}(G)/e$ bounded as $C\to\infty$), while a 'yes' answer would come from a lower-bound argument showing that any Ramsey host for a dense $G$ must itself contain many edges, e.g. via connectivity or expansion; small-case computation of $\hat{R}(G)$ for specific dense $G$ gives only weak evidence, since even modest size Ramsey numbers are hard to pin down exactly.

References

RefSourceType
REF-01 Erdős Problem #911 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.