Minimum Ramsey numbers for graphs with a prescribed number of edges

Abstract

For graphs A and B, the Ramsey number R(A, B) is the least N such that every red–blue colouring of the edges of KN contains a red A or a blue B. Write ρ(m) for the minimum of R(K3, G) over all finite simple graphs G with exactly m edges, with no connectedness assumption. Theorem. There is an absolute constant c > 0 such that every graph G with m edges satisfies R(K3, G) ≥ c m2/3/(log m)1/3 for all sufficiently large m. With Sudakov's clique-union upper bound this gives ρ(m) = Θ(m2/3/(log m)1/3). This proves the lower bound conjectured by Sudakov (SIAM J. Discrete Math. 21 (2007), p. 984), whose Theorem 1.1 left a factor (log m)1/3 between the two sides, improving in turn the bounds m3/5 << ρ(m) << m2/3 of Erdős, Faudree, Rousseau and Schelp. Application to Erdős Problem 1182. Let f(n) be the maximum number of edges of a connected n-vertex graph G with R(K3, G) = 2n − 1. The theorem gives f(n) = Θ(n3/2√(log n)), closing the interval n3/2(log n)1/2 << f(n) << n5/3(log n)2/3 of Burr, Erdős, Faudree, Rousseau and Schelp. The companion function F(n) is linear in n by their lower bound together with Brandt's F(n) ≤ 84n; that was already known, and is what answers the problem's final question, whether F(n)/n → ∞, in the negative. The order-of-magnitude question for f is what remained. Method. The lower bound comes from the early triangle-free process. For a fixed embedding of a graph H into the process graph, a martingale estimate tracks how many edges of that copy remain open; a matrix bound on the variance of the accumulated losses, in terms of Δ(H) and the maximum codegree of the process graph, yields an exponential tail strong enough to sum over all embeddings. This produces a triangle-free graph on N vertices whose complement contains no copy of H whenever e(H) ≥ Ak√(N log N) and Δ(H) ≤ N9/10. A deterministic subgraph argument then removes the maximum-degree restriction, which is what lets the bound apply to arbitrary G rather than only to graphs of bounded degree. The concentration estimates for the process are those of Bennett and Bohman. PDF and LaTeX source: github.com/FireflySentinel/erdos-1182. Use of generative AI. GPT-6 Astra was used to propose the mathematical proofs. GPT-5.6 Sol and Claude Opus 5 were used for editorial review of the exposition. The author finished the final manuscript and takes full responsibility for its content.