Prescribed Ramsey growth rate approximation

Conjecture 10 · arXiv:2311.01887

arXiv Conjecture high confidence— first stated 2023-11-03

Authors: Isabel Ahme, Alex Scott

Status open high confidence

Conjecture 10 from arXiv:2311.01887 asks whether every function f(n) satisfying n ≤ f(n) ≤ r(K_n) can be approximated to within a multiplicative factor of 1+ε by the Ramsey number of some n-vertex graph. The paper's main theorem achieves every such growth rate to within a multiplicative constant C_k, but the sharp 1+o(1) gap remains open. No follow-up paper resolving the conjecture was found in a broad literature search; the source paper itself appeared in print as Electronic Journal of Combinatorics 31(4) (2024).

Reviewer notes. No follow-up paper resolving Conjecture 10 was found. The precursor paper 'Ramsey Numbers with Prescribed Rate of Growth' (Pavez-Signé, Piga, Sanhueza-Matamala, arXiv:2209.05455, EJC 30(3) 2023) established growth rates up to a multiplicative constant, which Ahme–Scott improve by also controlling connectivity; Conjecture 10 asks for multiplicative gaps of 1+o(1). A 2024 Wigderson paper on Ramsey numbers upon vertex deletion (Journal of Graph Theory, 10.1002/jgt.23093) addresses related edge/vertex-deletion questions but does not resolve the conjecture. The conjecture is recent (posted 2023) and absence of evidence is strong evidence of it being open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For all functions $f(n) : \mathbb{N} \to \mathbb{N}$ with $n \leq f(n) \leq r(K_n)$ and for all $\varepsilon > 0$, there is a sequence of graphs $(G_n)_{n \in \mathbb{N}}$ satisfying $|V(G_n)| = n$ and $(1-\varepsilon)f(n) \leq r(G_n) \leq (1+\varepsilon)f(n)$ for all sufficiently large $n$.

Context

The paper's main theorem achieves every growth rate up to a multiplicative constant $C_k$; Conjecture 10 asks whether the multiplicative gaps in $\mathcal{R}^c_n$ can be made $1+o(1)$, i.e., whether any prescribed growth rate can be approximated arbitrarily closely. The authors suggest that edge-deletion results (such as a conjecture of Wigderson) might provide a route to this.

Notes. PDF source; mathematical notation is clean.

Source paper

Graphs with arbitrary Ramsey number and connectivity
Isabel Ahme, Alex Scott · 2023-11-03
https://arxiv.org/abs/2311.01887 PDF source