Existence of the Diagonal Ramsey Growth Limit

Existence of the Diagonal Ramsey Growth Limit

Definitions and mathematical statement

Let $R(k,k)$ be the least $N$ such that every red--blue coloring of the edges of the complete graph $K_N$ contains a monochromatic $K_k$. The question is whether the sequence of exponential growth scales has a limit: \[ \lim_{k\to\infty}R(k,k)^{1/k}. \] Equivalently, ask whether $k^{-1}\log R(k,k)$ converges. A proof need not identify the limit's exact value, but must rule out distinct subsequential limiting values. Bounds on the liminf and limsup, even improved exponential bounds, do not establish convergence unless the gap relevant to the limit is closed.

Formulation and concept references: [S1].

Short English statement

Does the exponential growth rate of the diagonal two-color Ramsey numbers settle to a single constant?

Research attempt

Scope and checked literature (27 September 2026).

The target is existence of an exponential growth rate, not its numerical value. The problem page [S1] retains precisely that distinction. The primary paper of Gupta, Ndiaye, Norin, and Wei [E1] gives an improved exponential upper bound; its abstract states $R(k,k)\leq3.8^{k+o(k)}$. We use that conservative stated bound only as context, not as a claim of the best current numerical constant. It does not assert that the lower and upper exponential growth rates coincide.

This attempt reconstructs the elementary bounds, tests the natural graph-product route, and proves a precise conditional convergence lemma. It also constructs a monotone integer sequence showing why exponential bounds and controlled successive growth are insufficient on their own. All logarithms below are natural logarithms.

Basic bounds, with their quantifiers.

Let $R(s,t)$ be the least order forcing either a red $K_s$ or a blue $K_t$. Looking at the red and blue neighborhoods of one vertex gives \begin{equation}\label{wsref-0-61-34-36-39-3a-72-65-63-75-72-72-65-6e-63-65} R(s,t)\leq R(s-1,t)+R(s,t-1). \end{equation} Indeed among the other $R(s-1,t)+R(s,t-1)-1$ vertices, either at least $R(s-1,t)$ join the chosen vertex in red or at least $R(s,t-1)$ join it in blue. The corresponding Ramsey property supplies the desired monochromatic clique. Starting with $R(1,t)=R(s,1)=1$, induction and Pascal's identity give \[ R(s,t)\leq\binom{s+t-2}{s-1},\qquad R(k,k)\leq\binom{2k-2}{k-1}\leq4^{k-1}. \] These inequalities also prove that the Ramsey numbers in question are finite.

For a lower bound, color every edge of $K_N$ independently red or blue with equal probability. A given $k$-set is monochromatic with probability $2^{1-\binom{k}{2}}$. If \[ N=\left\lfloor2^{(k-1)/2}\right\rfloor, \] then for $k\geq3$ the expected number of monochromatic $k$-sets is at most \[ \frac{N^k}{k!}\,2^{1-k(k-1)/2}\leq\frac2{k!}<1. \] Some coloring therefore has none, so $R(k,k)>N$. It follows that \begin{equation}\label{wsref-0-61-34-36-39-3a-62-6f-75-6e-64-73} \sqrt2\leq\liminf_{k\to\infty}R(k,k)^{1/k} \leq\limsup_{k\to\infty}R(k,k)^{1/k}\leq4. \end{equation} One may replace the last bound by the improved constant from [E1]. Such replacement shrinks a permitted interval; it does not establish that its endpoints are equal. Since exponentiation is continuous and strictly increasing on the bounded logarithmic interval, existence of the requested limit is equivalent to convergence of $\log R(k,k)/k$.

Lemma 469.1: the exact graph-product inequality.

Encode red edges by a simple graph $G$, with blue edges its complement. Write $\omega(G)$ for the clique number and $\alpha(G)$ for the independence number. The lexicographic product $G[H]$ has vertices $(g,h)$; two distinct vertices are adjacent when their first coordinates are adjacent in $G$, or their first coordinates agree and their second coordinates are adjacent in $H$. Then \begin{equation}\label{wsref-0-61-34-36-39-3a-70-72-6f-64-75-63-74-6e-75-6d-62-65-72-73} \omega(G[H])=\omega(G)\omega(H),\qquad \alpha(G[H])=\alpha(G)\alpha(H). \end{equation} For a clique, the occupied first-coordinate fibers form a clique of $G$, and each fiber contributes at most $\omega(H)$ vertices. Taking maximum cliques in those fibers attains the product. For independent sets the same argument applies with nonadjacent first coordinates and independent sets in each fiber. Alternatively complementation commutes with the lexicographic product.

Choose extremal colorings witnessing $R(a+1,a+1)-1$ and $R(b+1,b+1)-1$. Formula (a469:productnumbers) yields \begin{equation}\label{wsref-0-61-34-36-39-3a-77-72-6f-6e-67-70-61-72-61-6d-65-74-65-72} R(ab+1,ab+1)-1\geq (R(a+1,a+1)-1)(R(b+1,b+1)-1). \end{equation} This is a genuine supermultiplicative statement, but the clique thresholds multiply. Fekete's lemma for $\log R(k,k)$ would need information comparing the index $a+b$ with $a$ and $b$, up to a controlled error. Substituting (a469:wrongparameter) as though its index were $a+b$ is invalid.

The five-cycle makes the distinction visible. Both its clique and independence numbers are two. Its $t$-fold lexicographic power has $5^t$ vertices and both parameters $2^t$. Hence \[ R(2^t+1,2^t+1)>5^t. \] This is only a polynomial lower bound when expressed in the clique threshold $2^t$, since $5^t=(2^t)^{\log_2 5}$. Iterating this particular product loses to the elementary exponential first-moment bound. This calculation does not exclude other product constructions; it establishes exactly what this one supplies.

Proposition 469.2: a bounded additive defect would suffice.

Put $a_n=\log R(n,n)$. Suppose, as an additional hypothesis, that there is a constant $C\geq0$ independent of $m,n$ such that \begin{equation}\label{wsref-0-61-34-36-39-3a-64-65-66-65-63-74} a_{m+n}\geq a_m+a_n-C \quad(m,n\geq1). \end{equation} Then $a_n/n$ has a finite limit. To prove this, set $b_n=a_n-C$. The hypothesis says $b_{m+n}\geq b_m+b_n$. The elementary upper bound makes $\sup_n b_n/n$ finite. Fix $k$, and write $n=qk+r$ with $0\leq r<k$. Repeated superadditivity gives $b_n\geq q b_k+b_r$ when $r>0$, and $b_n\geq q b_k$ when $r=0$. Since the finitely many remainder terms are bounded below, \[ \liminf_{n\to\infty}\frac{b_n}{n} \geq\frac{b_k}{k}. \] Taking the supremum over $k$ and comparing with the definition of that supremum proves convergence. Since $C/n\to0$, the conclusion holds for $a_n/n$ as well. Exponentiating proves existence of the target root limit.

The uniformity of $C$ is indispensable to this proof. Replacing it by an error of order $m+n$ can accumulate a linear loss every time blocks are combined, and does not yield this lemma. A sufficiently controlled smaller error may support a different almost-superadditive theorem, but such a bound must itself be established, including how the errors accumulate. Neither the off-diagonal recurrence (a469:recurrence) nor (a469:wrongparameter) establishes (a469:defect).

Thus a concrete possible research objective is a construction preserving red and blue clique avoidance under an operation whose forbidden clique sizes add, while the vertex counts multiply up to an absolute factor. Its uniform factor would give (a469:defect). The lexicographic construction fails at precisely the required additive-parameter condition. This attempt supplies no replacement operation satisfying it.

A counterexample to inference from coarse regularity alone.

One might hope that monotonicity, exponential upper and lower bounds, and bounded ratios of consecutive terms force an exponential rate. They do not. Define \[ f(x)=x\left(c+d\sin\log x\right),\qquad c=\log2,\quad d=\frac1{10},\qquad A_n=\left\lceil\exp(f(n))\right\rceil. \] The function is strictly increasing because \[ f'(x)=c+d\sin\log x+d\cos\log x\geq c-\sqrt2d>0. \] Thus $(A_n)$ is a nondecreasing sequence of positive integers. It has exponential bounds \[ e^{(c-d)n}\leq A_n\leq e^{(c+d)n}+1, \] and bounded consecutive ratios. Indeed the mean value theorem gives $f(n+1)-f(n)\leq c+\sqrt2d$, so \[ \frac{A_{n+1}}{A_n} \leq e^{c+\sqrt2d}+e^{-f(n)} \leq e^{c+\sqrt2d}+1. \] Nevertheless \[ \frac{\log A_n}{n} =c+d\sin\log n+o(1) \] does not converge. Choose integers nearest to $\exp(\pi/2+2\pi j)$ and to $\exp(3\pi/2+2\pi j)$. The rounding changes their logarithms by a quantity tending to zero, so the two subsequences approach $c+d$ and $c-d$, respectively. The $n$th roots therefore have distinct subsequential limits $e^{c+d}$ and $e^{c-d}$.

This sequence is not asserted to be a Ramsey sequence, and it need not satisfy the full off-diagonal recurrence of Ramsey numbers. Its exact purpose is to refute an argument using only the three coarse properties just proved for it. The combinatorial structure of Ramsey colorings must do further work. Merely recognizing smooth-looking finite data or bounded successive growth is not that additional work.

Exact finite diagnostics.

The accompanying integer program verifies $R(3,3)=6$ directly: the red five-cycle on five vertices has neither a red nor a blue triangle, and exhaustive examination of all $2^{15}$ red-edge sets on six vertices finds a monochromatic triangle in every case. Independently, the standard short proof observes that some vertex of $K_6$ has at least three neighbors in one color; an edge of that color among them completes a triangle, while its absence makes those three a triangle of the other color.

The program also constructs $C_5[C_5]$ on 25 vertices. It enumerates its $\binom{25}{5}$ five-vertex subsets, finds none that is a clique or an independent set, and records explicit four-vertex examples of both. This checks the product interpretation behind $R(5,5)\geq26$. It is not a claim of the exact value of $R(5,5)$, and the deliberately weak bound is used solely to verify the proposed operation.

The recurrence's binomial bounds and the first-moment inequalities are checked on a finite range as arithmetic diagnostics. Their proofs above, not that range, establish their uniform validity. No finite list of Ramsey values proves the uniform defect estimate (a469:defect) or existence of a limiting growth rate.

Status and next mathematical step.

The attempt establishes nontrivial exponential bounds, an exact multiplicative-threshold construction, and a sufficient bounded-defect theorem. It also isolates two failed routes: applying an additive-index convergence theorem to a multiplicative-index graph product, and deriving convergence from monotonicity plus exponential envelopes. The missing ingredient is an asymptotic structural relation strong enough to identify the liminf and limsup of $\log R(k,k)/k$. Improved one-sided constants, including [E1], do not currently supply that relation within this argument. The requested existence statement remains unresolved here.

UNRESOLVED. The partial results above do not establish the full selected statement.

Sources

• S1 T. F. Bloom (maintainer), Erdős Problems database, #77; Erdős source references cited there: [Er61], [Er69b], [Er71, p.99], [Er81], [Er88, p.83], [Er90b, p.17], [Er93, p.338], [Er95], [Er97c], [Er97d], [Va99, 3.50]. https://www.erdosproblems.com/77. Formulation source.
• E1 P. Gupta, N. Ndiaye, S. Norin, and L. Wei, "Optimizing the CGMS upper bound on Ramsey numbers," arXiv:2407.19026. https://arxiv.org/abs/2407.19026. Primary improved upper-bound result; its numerical improvement is distinguished from existence of an exponential growth limit. Checked 27 September 2026.