ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1030 · PARTIAL

Erdős problem #1030 — wave 6s

Access date: 2026-07-27 UTC.

Outcome

I did not prove the requested asymptotic statement. I obtained four verifiable outputs.

  1. [b, source correction] The live page understates its own cited 1989

result. It says \[ R(k+1,k)-R(k,k)\geq 2k-5, \] but Burr--Erdős--Faudree--Schelp actually prove the stronger \[ R(k+1,k)-R(k,k)\geq 2k-3. \]

  1. [a, reconstructed construction] Xu--Shao--Radziszowski (2011), not

mentioned on the live page, improve this for every \(k\geq5\) to \[ \boxed{R(k+1,k)-R(k,k)\geq2k-2}. \] I give the complete specialised construction and proof below; the standalone program builds and checks it.

  1. [a, exact method barrier] The increment \(2k-2\) is the largest

possible increment obtainable from any adjacent-parameter specialisation of Xu--Shao--Radziszowski Theorem 3. Its best relative increment tends to zero exponentially, so that construction theorem cannot prove #1030.

  1. [a, clean sufficient reduction] A proportional gap follows from an

explicit 0--1 packing problem on the large cliques of one diagonal Ramsey-critical graph. This gives a concrete missing structural lemma, rather than simply restating the target Ramsey inequality.

  1. [a/b] The exact initial ratios are

\[ \frac{R(3,2)}{R(2,2)}=\frac32,\qquad \frac{R(4,3)}{R(3,3)}=\frac32,\qquad \frac{R(5,4)}{R(4,4)}=\frac{25}{18}. \] The first two and \(R(4,4)=18\) have elementary reductions checked below. The equality \(R(4,5)=25\) is [b], relying on the named 2024 HOL4 theorem; the supplied program independently checks its explicit 24-vertex lower witness but does not pretend to replay the large HOL4 upper-bound computation.

Claim labels used throughout are:

0. Mandatory live-page gate

[b, live-source audit] I accessed all of the following through the Bright Data residential browser, rather than relying on the stale tracker YAML:

The rendered page reported:

The first comment, by Ryan Tuck at 20:56 on 23 March 2026, asks that the Ramsey-number definition and the endpoint of the limit be made explicit. It also links a formal-conjectures pull request, but does not claim to work on a proof of this problem. Thomas Bloom replies at 21:07 that \(R(k,l)\) is the usual off-diagonal Ramsey number and that the limit is \(k\to\infty\). Neither comment is a proof claim or a current-worker marker. Thus the mandatory stop condition did not fire.

Verbatim current statement

The live LaTeX view gives:

Let \(R(k,l)\) be the usual Ramsey number: the smallest \(n\) such that if the edges of \(K_n\) are coloured red and blue then there exists either a red \(K_k\) or a blue \(K_l\).

Prove the existence of some \(c>0\) such that \[ > \lim_{k\to \infty}\frac{R(k+1,k)}{R(k,k)}> 1+c. > \]

I retain the literal lim. The comment clarifies its endpoint but does not replace it by liminf; consequently, a literal solution must also establish existence of the displayed ratio limit.

Results listed by the live page

[b, as stated by the page] The page says that Erdős and Sós could not prove

\[ R(k+1,k)-R(k,k)>k^c \]

for any \(c>1\). It lists the elementary bound \(k-2\), attributes the bound \(2k-5\) to Burr--Erdős--Faudree--Schelp, and points to problems #544 and #1014. Section 1 below checks the cited primary paper and finds that the displayed \(2k-5\) is not the theorem in that paper.

1. Primary-source literature audit

1.1 The original local-growth conjectures

[b] Paul Erdős, Some new problems and results in graph theory and other branches of combinatorial mathematics, LNM 885 (1981), 9--17, DOI 10.1007/BFb0092251, Erdős archive scan, exists and discusses this exact local-growth problem on printed page 11. It records:

\(R(n+1,n)>(1+c)R(n,n)\);

\[ \frac{R(n+1,n)-R(n,n)}{n}\longrightarrow\infty; \]

\(C=\lim R(n,n)^{1/n}\), then the ratio in #1030 should tend to \(C^{1/2}\).

[b] Xu--Shao--Radziszowski later report that, between 2007 and 2009, they asked several of Erdős's collaborators about the claimed proof of the second assertion; nobody could recall it, so they advise treating it as a conjecture. The April 2026 revision of the small-Ramsey-number survey likewise says only easy bounds on these differences are known.

1.2 What the 1989 paper actually proves

[b] S. A. Burr, P. Erdős, R. J. Faudree, and R. H. Schelp, On the difference between consecutive Ramsey numbers, Utilitas Mathematica 35 (1989), 115--118, primary PDF, states as Theorem 1

\[ R(m,n)\geq R(m,n-1)+2m-3. \]

[a, substitution into the named theorem] By symmetry,

\[ \begin{aligned} R(k+1,k)-R(k,k) &=R(k,k+1)-R(k,k)\\ &\geq2k-3. \end{aligned} \]

Thus the live page's \(2k-5\) is two smaller than the cited theorem. This is a correction of page metadata, not a solution of the asymptotic problem.

1.3 The stronger 2011 construction

[b] X. Xu, Z. Shao, and S. P. Radziszowski, More constructive lower bounds on classical Ramsey numbers, SIAM Journal on Discrete Mathematics 25 (2011), 394--400, DOI 10.1137/10080868X, author-hosted PDF, proves as Corollary 3

\[ R(k,s+1)\geq R(k,s)+2k-2\qquad(k\geq5). \]

Putting \(s=k\) and using symmetry gives the boxed \(2k-2\) bound in the Outcome.

1.4 Current-state check

[b] S. P. Radziszowski, Small Ramsey Numbers, revision DS1.18, 24 April 2026, primary survey PDF, section 2.3(e), still describes the superlinear-difference question as open and says only easy bounds are known.

[b] M. Liang, S. P. Radziszowski, and X. Xu, On a Diagonal Conjecture for Classical Ramsey Numbers, arXiv:1810.11386, DOI 10.1016/j.dam.2019.07.006, also discusses consecutive differences and explicitly says that the comparison resists known methods. Its arXiv text was updated on 22 March 2026, but it does not settle #1030.

I searched exact variants of R(k+1,k), R(k,k), “consecutive Ramsey numbers,” and “difference,” inspected the papers above, and performed a forward-citation sweep from the 2011 DOI. I found papers on the fixed-\(3\) Erdős--Sós problem, constructive finite bounds, and the Diagonal Conjecture, but no later primary source proving a superlinear bound here. This is an honest literature-search miss, not a proof that no unindexed result exists.

2. Reconstructed adjacent-parameter construction

Call a graph \(G\) a \((q,s)\)-graph when

\[ \omega(G)<q,\qquad \alpha(G)<s. \]

Such a graph on \(N\) vertices certifies \(R(q,s)>N\).

2.1 A critical graph contains the needed core

[a] Lemma 1. Every Ramsey-critical \((k,s)\)-graph contains a \(K_{k-1}\).

Proof. Let \(r=R(k-1,s)\), and take a \((k-1,s)\)-graph on \(r-1\) vertices. Adding one universal vertex produces a \((k,s)\)-graph on \(r\) vertices, so

\[ R(k,s)\geq R(k-1,s)+1. \]

A critical \((k,s)\)-graph therefore has \(R(k,s)-1\geq r\) vertices. If it contained no \(K_{k-1}\), it would itself be a \((k-1,s)\)-graph on at least \(r\) vertices, contradicting the definition of \(r\). \(\square\)

2.2 Explicit gadget

Fix \(k\geq5\). Let \(G\) be any \((k,s)\)-graph containing a labelled clique

\[ U_0=\{u_0,\ldots,u_{k-2}\}\cong K_{k-1}. \]

Write all of \(V(G)\) as \(U\), and create two new sets

\[ V=\{v_0,\ldots,v_{k-2}\},\qquad W=\{w_0,\ldots,w_{k-2}\}. \]

Define \(F\) as follows.

  1. Keep \(G\) on \(U\), and make \(V\) a \(K_{k-1}\).
  2. Split \(W\) into

\[ W_1=\{w_0,w_1\},\qquad W_2=\{w_2,\ldots,w_{k-2}\}. \] Make each \(W_i\) a clique and put no edges between \(W_1\) and \(W_2\).

  1. The only \(U\)-to-\(V\) edges are the matching edges \(u_iv_i\).
  2. Join \(w_i\) to \(u_j\) precisely when

\(i\ne j\) and \(u_iu_j\in E(G)\).

  1. Join \(w_i\) to \(v_j\) precisely when \(i\ne j\).

This is exactly the \(t=2\), \(H=M=K_{k-1}\) specialisation of the 2011 construction, written without invoking its general notation.

2.3 Clique check

[a] Lemma 2. \(F\) contains no \(K_k\).

Proof. Suppose a clique \(Q\) meets both \(U\) and \(V\). The only edges between these sets form a matching, so

\[ Q\cap(U\cup V)=\{u_i,v_i\} \]

for one \(i\). Since there are no \(W_1\)-to-\(W_2\) edges, the rest of \(Q\) lies in one \(W_j\). Every \(w_h\) in it must have \(h\ne i\). For \(k\geq5\),

\[ \max(|W_1|,|W_2|)=k-3, \]

and hence \(|Q|\leq2+(k-3)=k-1\).

If \(Q\) does not meet both \(U\) and \(V\), replace every \(w_i\in Q\) by the corresponding \(u_i\) (on the \(U\) side) or \(v_i\) (on the \(V\) side). The replacement is injective because \(w_i\) is adjacent to neither \(u_i\) nor \(v_i\), and the defining mirrored adjacencies make the image a clique of the same size in \(G\) or \(K_{k-1}\). Its size is therefore at most \(k-1\). \(\square\)

2.4 Independence check

[a] Lemma 3. If \(\alpha(G)\leq s-1\), then \(\alpha(F)\leq s\).

Proof. Let \(I\) be independent in \(F\), with parts \(I_U,I_V,I_1,I_2\) in \(U,V,W_1,W_2\). For \(r=1,2\), let \(C_r\) be the selected \(U\)- or \(V\)-vertices whose corresponding \(w_i\) lies in \(I_r\).

Partition \(I\) into

\[ \begin{aligned} A&=I_1\cup C_2\cup \bigl(I_U\setminus(C_1\cup C_2)\bigr),\\ B&=I_2\cup C_1\cup \bigl(I_V\setminus(C_1\cup C_2)\bigr). \end{aligned} \]

Map \(A\) injectively into \(G\) by sending every indexed \(w_i,u_i,v_i\) to \(u_i\), and leaving the unindexed \(U\)-vertices where they are. Injectivity follows because \(w_i\) is adjacent to neither corresponding copy, while \(u_i v_i\) is a matching edge. The mirrored-edge rule makes the image independent; when a selected \(v_i\in C_2\) is mapped to \(u_i\), the simultaneously selected \(w_i\in I_2\) certifies all required nonadjacencies to the other mapped vertices. Thus

\[ |A|\leq\alpha(G)\leq s-1. \]

Similarly, map \(B\) into the complete graph on \(V\), sending its indexed vertices to \(v_i\). Its image is independent, so \(|B|\leq1\). The two sets partition \(I\), whence \(|I|\leq s\). \(\square\)

2.5 Ramsey consequence

[a] Theorem 4. For \(k\geq5\) and \(s\geq2\),

\[ R(k,s+1)\geq R(k,s)+2k-2. \]

Proof. Take a critical \((k,s)\)-graph \(G\) on \(R(k,s)-1\) vertices. Lemma 1 supplies the \(K_{k-1}\) core. The construction adds \(2(k-1)\) vertices, and Lemmas 2--3 show that the resulting

\[ R(k,s)-1+2(k-1)=R(k,s)+2k-3 \]

vertex graph is a \((k,s+1)\)-graph. Add one to its order to obtain the Ramsey lower bound. \(\square\)

Taking \(s=k\) and \(R(k,k+1)=R(k+1,k)\) proves

\[ R(k+1,k)-R(k,k)\geq2k-2\qquad(k\geq5). \]

3. Exact ceiling of this construction family

[a] Proposition 5. The increment \(2k-2\) is optimal among all applications of Xu--Shao--Radziszowski Theorem 3 which start with a critical \((k,s)\)-graph and target \((k,s+1)\).

Proof. That theorem combines a \((k,s)\)-graph \(G\), a \((k,t)\)-graph \(H\), and a common induced graph \(M\), and targets the second parameter \(s+t-1\). To obtain \(s+1\), necessarily

\[ t=2. \]

Since \(\alpha(H)<2\), \(H\) is complete. Since \(\omega(H)<k\), its order \(h\) satisfies \(h\leq k-1\). The common induced graph has order \(m\leq h\leq k-1\).

Starting with the largest possible seed, of order \(R(k,s)-1\), the theorem therefore adds at most

\[ h+m\leq2k-2 \]

to the resulting Ramsey lower bound. Equality is attained by \(H=M=K_{k-1}\), exactly as in Section 2. \(\square\)

The relative-gain wall

[a] A random red/blue coloring of \(K_n\) has expected number of monochromatic \(K_k\)'s

\[ 2\binom nk2^{-\binom k2}. \]

For \(n=\lfloor2^{k/2}\rfloor\),

\[ 2\binom nk2^{-\binom k2} \leq \frac{2^{1+k/2}}{k!}<1\qquad(k\geq4). \]

Thus

\[ R(k,k)>\lfloor2^{k/2}\rfloor. \]

Consequently the largest relative increment certified by the entire construction family in Proposition 5 obeys

\[ 0\leq\frac{2k-2}{R(k,k)} <\frac{2k-2}{\lfloor2^{k/2}\rfloor} \longrightarrow0. \]

This is an exact obstruction to that method, not evidence that the true ratio tends to one.

4. A non-additive true-twin packing reduction

The preceding construction is forced to add only \(O(k)\) vertices. There is a different, genuinely non-additive route which turns the missing step into a concrete packing problem.

Let \(G\) be a \((k,k)\)-graph and let \(S\subseteq V(G)\). Form \(G^S\) by replacing every vertex in \(S\) by a two-vertex clique of true twins, every other vertex by a singleton, and putting a complete or empty bipartite graph between two fibres according as their original vertices are adjacent or nonadjacent in \(G\).

[a] Proposition 6 (exact blow-up formulas).

\[ \alpha(G^S)=\alpha(G) \]

and

\[ \omega(G^S) =\max_{\substack{C\subseteq V(G)\\C\text{ a clique}}} \bigl(|C|+|C\cap S|\bigr). \]

Proof. An independent set uses at most one vertex from each clique fibre, and its projection is independent in \(G\); conversely every independent set of \(G\) lifts by choosing one representative per fibre. A clique projects to a clique \(C\) of \(G\), and it may use both vertices precisely in the fibres indexed by \(C\cap S\). Taking all allowed fibre vertices attains the displayed maximum. \(\square\)

It follows that \(G^S\) is a \((k+1,k)\)-graph exactly when

\[ \boxed{\ |C\cap S|\leq k-|C|\quad\text{for every clique }C\text{ of }G.\ } \tag{TP} \]

The constraint is automatic for \(|C|\leq\lfloor k/2\rfloor\), so (TP) is a finite 0--1 packing problem involving only the larger cliques of \(G\).

[a, fractional diagnostic] In the linear-programming relaxation of (TP), the uniform assignment

\[ x_v=\frac1{k-1}\qquad(v\in V(G)) \]

is always feasible. Indeed, for a clique of order \(r\leq k-1\),

\[ \frac{r}{k-1}\leq k-r. \]

It has fractional value \(|V(G)|/(k-1)\). Thus even a constant-factor rounding theorem for this particular clique-capacity system would give an integral packing of exponential-over-polynomial order and would already prove the still-open \((R(k+1,k)-R(k,k))/k\to\infty\). The possible integrality gap is therefore a precise obstruction; this observation does not supply the rounding theorem or the constant-density packing needed for #1030.

[a] Corollary 7. If \(G\) is Ramsey-critical for \((k,k)\) and \(S\) satisfies (TP), then

\[ R(k+1,k)\geq R(k,k)+|S|. \]

In particular, sets satisfying

\[ |S|\geq\varepsilon R(k,k) \]

for some fixed \(\varepsilon>0\) and all large \(k\) would prove the corresponding liminf separation in #1030.

Proof. The blow-up has

\[ |V(G^S)|=R(k,k)-1+|S|, \]

has independence number at most \(k-1\), and has clique number at most \(k\) by (TP). It is therefore a lower-bound witness for \(R(k+1,k)\).

\(\square\)

[a, exact obstruction inside this ansatz] If every edge of \(G\) lies in a \(K_{k-1}\), then (TP) forces \(S\) to be independent: a \(K_{k-1}\) may contain at most one selected vertex. Hence

\[ |S|\leq\alpha(G)\leq k-1. \]

Thus this route needs a diagonal critical graph with a positive-density packing which evades the capacities of all its large cliques. No theorem found in the audit supplies such a graph or packing. This is a sufficient reduction, not an assertion that every possible solution must have this form, and it still does not establish existence of the literal limit.

[d] As finite sanity checks, the standalone program solves (TP) by complete enumeration for the \(C_5\) diagonal witness at \(k=3\) and the Paley-17 diagonal witness at \(k=4\). Their optimum packing sizes are 2 and 3, respectively; the corresponding true-twin blow-ups have \((\omega,\alpha)=(3,2)\) on 7 vertices and \((4,3)\) on 20 vertices. These small values are checks of the reduction, not asymptotic evidence.

5. Exact initial cases

\(k\)\(R(k,k)\)\(R(k+1,k)\)ratiostatus
223\(3/2\)[a]
369\(3/2\)[a]
41825\(25/18\)[a] denominator; [b] numerator

[a] \(R(q,2)=q\) directly from the definition.

[a] The checker exhausts all \(2^{15}=32768\) labelled graphs on six vertices, finds no \((3,3;6)\)-graph, and finds exactly 12 labelled \((3,3;5)\)-graphs (the labelled 5-cycles). Hence \(R(3,3)=6\).

[a] The complement of the eight-vertex Möbius ladder has \((\omega,\alpha)=(3,2)\), proving \(R(4,3)>8\). In a hypothetical \((4,3;9)\)-graph, every vertex has degree at most five because its neighborhood is a \((3,3)\)-graph. Its antineighborhood is a clique of order at most three, so every degree is also at least five. All nine degrees would equal five, contradicting the handshake lemma. Thus \(R(4,3)=9\).

[a] The Paley graph on \(\mathbb F_{17}\) has \((\omega,\alpha)=(3,3)\), checked from its quadratic-residue definition, so \(R(4,4)>17\). In a hypothetical \((4,4;18)\)-graph, a vertex neighborhood has at most \(R(3,4)-1=8\) vertices, and its antineighborhood has at most \(R(4,3)-1=8\). These two sets would have to contain all 17 other vertices, a contradiction. Hence \(R(4,4)=18\).

[b] T. Gauthier and C. E. Brown, A Formal Proof of \(R(4,5)=25\), DOI 10.4230/LIPIcs.ITP.2024.16, arXiv:2404.01761, formally verify \(R(4,5)=25\) in HOL4. The standalone checker imports their published 24-by-24 witness matrix from the accompanying repository and independently recomputes \((\omega,\alpha)=(3,4)\), proving the lower side \(R(4,5)>24\). The upper side remains explicitly modulo their named formal theorem.

No uniform conclusion may be drawn from three exact ratios.

6. Standalone verifier

The self-contained standard-library program is erdos1030_wave6s_reverify.py. It implements its own bitset maximum-clique search and separately cross-checks the finite witnesses by direct subset enumeration; no SAT package, graph package, or download is trusted at run time.

Run from the repository root:

python runs/erdos1030_wave6s_reverify.py

Observed output:

R(3,3)=6: exhaustive labelled-graph check passed
R(4,3)=9 and R(4,4)=18: witnesses and elementary reductions passed
R(4,5)>24: explicit 24-vertex witness has (omega,alpha)=(3,4)
R(4,5)<=25: EXTERNAL HOL4 theorem; not recomputed by this script
XSR K_{k-1}-seed checks (k,n,omega,alpha): [(5, 12, 4, 2), (6, 15, 5, 2), (7, 18, 6, 2), (8, 21, 7, 2), (9, 24, 8, 2), (10, 27, 9, 2), (11, 30, 10, 2), (12, 33, 11, 2)]
XSR exhaustive fixed-K4/two-extra stress tests passed: 446
True-twin checks (seed,n,packing,omega,alpha): [('C5', 5, 2, 3, 2), ('Paley17', 17, 3, 4, 3)]
Adjacent XSR ceiling max(h+m)=2k-2 verified for 5<=k<=100
Random-colouring denominator and vanishing-relative-gain arithmetic passed
ALL CHECKS PASSED

The 446 stress tests are all admissible labelled graphs formed from a fixed \(K_4\) and two extra vertices; the other 66 of the \(2^9=512\) possibilities contain a \(K_5\) and correctly fail the seed hypothesis.

7. Precise remaining wall and compute cost

Define the exact extremal quantities

\[ \begin{aligned} N_k&=\max\{|V(G)|:\omega(G)\leq k-1,\ \alpha(G)\leq k-1\} =R(k,k)-1,\\ M_k&=\max\{|V(G)|:\omega(G)\leq k,\ \alpha(G)\leq k-1\} =R(k+1,k)-1. \end{aligned} \]

Then the displayed ratio is exactly

\[ \frac{M_k+1}{N_k+1}. \]

[a] The construction above proves only

\[ M_k\geq N_k+2k-2. \]

To obtain a fixed multiplicative gap, the missing mathematical input is a uniform theorem of the scale

\[ M_k\geq(1+\varepsilon)N_k+O(1) \]

for some \(\varepsilon>0\). To meet the live statement literally, one must also prove that \((M_k+1)/(N_k+1)\) has a limit. No construction or theorem found in the literature audit supplies either ingredient.

[d, cost evidence] A raw SAT encoding of just \(R(4,4)\leq18\) did not finish in a deliberately capped 180-second local trial; I discarded it rather than treating solver silence as evidence. The elementary reduction in Section 5 is the actual certificate.

[d, published reproducibility cost] Even the finite theorem \(R(4,5)=25\) is substantial. Gauthier--Brown report running the final formal gluing phase on four 512--1024 GB machines, 40 cores per machine, for under nine days, and producing roughly a petabyte of proof files. The time ceiling is about

\[ 4\cdot40\cdot9\cdot24=34560\ \text{core-hours}. \]

At an illustrative \(0.05\)--\(0.10\) USD per core-hour this is \(\$1.7\)k--\(\$3.5\)k for CPU alone; suitable high-memory instances and petabyte-scale storage would dominate that estimate. Replaying it is far beyond this VM and would not address the asymptotic problem.

[a, asymptotic cost diagnosis] Since already \(R(k,k)>2^{k/2}\), brute-force enumeration at the relevant order has at least

\[ 2^{\binom{\lfloor2^{k/2}\rfloor}{2}} =2^{\Omega(2^k)} \]

edge colorings. Thus finite enumeration cannot provide the required uniformity step. The exact missing object is a non-additive construction or structural lemma giving \(\Omega(N_k)\), rather than \(O(k)\), new vertices while increasing the permitted clique size by only one and leaving the independence threshold fixed.

PARTIAL: verified the omitted stronger linear bound \(R(k+1,k)-R(k,k)\geq2k-2\) for \(k\geq5\), proved its optimality within the Xu--Shao--Radziszowski adjacent construction family, and reduced a proportional gap to an explicit true-twin clique-packing lemma whose uniform and limit-existence steps remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger