Erdős problem #812 — verified wave 6m report
Date of audit: 2026-07-27 (UTC).
0. Mandatory live-page check
I fetched https://www.erdosproblems.com/812 through the Bright Data browser, not
with datacenter curl. I checked the rendered body twice, and separately opened
the page's bibliography widgets. The live page says OPEN.
The live statement, verbatim (only typesetting has been restored), is:
> Is it true that
> \[ > \frac{R(n+1)}{R(n)}\geq 1+c > \]
> for some constant \(c>0\), for all large \(n\)? Is it true that
> \[ > R(n+1)-R(n)\gg n^2? > \]
The page attributes the question to [Er91] and gives the following known
results:
> Burr, Erdős, Faudree, and Schelp [BEFS89] proved that
> \[ > R(n+1)-R(n)\geq 4n-8 > \]
> for all \(n\geq 2\). The lower bound of [165] implies that
> \[ > R(n+2)-R(n)\gg n^{2-o(1)}. > \]
All collaboration/proof markers were also checked:
| live-page field | rendered value |
|---|---|
| comments | 0 |
| claimed proofs | 0 |
| interested in collaborating | None |
| currently working | None |
| likes | Alfaiz, Dogmachine |
| looks difficult | Dogmachine |
| looks tractable | None |
| results could be formalisable | None |
| working on formalising | None |
Thus neither mandatory stop condition was present. The page additionally says
“Formalised statement? Yes” and lists OEIS A059442.
The [Er91] widget identifies the original source as P. Erdős, *Problems and
results in combinatorial analysis and combinatorial number theory, in Graph
Theory, Combinatorics, and Applications*, Vol. 1 (Kalamazoo, MI, 1988), 1991,
pp. 397–406, MR 1170793. I verified that bibliographic record, but did not locate
a reliable full scan during this run; consequently, the live page—not an
inferred recollection of Er91—is the ground truth for the statement above.
Notation and claim labels
Write \(r(s,t)\) for the least \(N\) such that every red/blue coloring of
\(K_N\) has a red \(K_s\) or a blue \(K_t\), and write
\[ R(n)=r(n,n),\qquad \Delta_n=R(n+1)-R(n),\qquad q_n=\frac{R(n+1)}{R(n)}. \]All logarithms below are natural; changing their base only changes constants.
The requested labels are:
- [a] elementary-rigorous: a complete proof is given here;
- [b] rigorous-modulo-named-theorem: the deduction is complete, conditional
only on the explicitly named published theorem or preprint theorem;
- [c] plausible/structural-unverified: heuristic or proposed missing
structure, not used as a theorem;
- [d] computational-only: established by the supplied exhaustive program.
Primary-source audit
The exact local source snapshots are in runs/references/erdos812/. The
standalone verifier checks both these hashes and theorem-identifying text:
| source | theorem actually used | SHA-256 of local PDF |
|---|---|---|
| Burr–Erdős–Faudree–Schelp, On the Difference between Consecutive Ramsey Numbers, Utilitas Math. 35 (1989), 115–118 | Theorems 1 and 2 | af628d8b55528af76dc01fc5cbe3e84b69fad16423d6312707230c8ec0e58917 |
| Mattheus–Verstraëte, The asymptotics of \(r(4,t)\), Annals of Mathematics 199 (2024), 919–941; arXiv:2306.04007 | \(r(4,t)=\Omega(t^3/\log^4t)\) | a7fbe45d82fae54023d04f9d65429b533b987ae6f6345b5978540fba067688cf |
| Hefty–Horn–King–Pfender, Improving \(R(3,k)\) in just two bites, arXiv:2510.19718v3 | Theorem 1.2, \(r(3,k)\geq(\tfrac12+o(1))k^2/\log k\) | eeae0baea15768f450ab0d4f21c0f12d40a882e53d2ee7924c3af2090f156792 |
| Bradač, Off-diagonal Ramsey numbers, arXiv:2605.28793v3 | Theorem 1.1, \(r(s,k)\geq c_s k^{s-1}/(\log k)^{2s-4}\) | d48fe98641118a52022bcff035955b2e320a88537f25917ed98e9f5c845f8fa5 |
The Mattheus–Verstraëte theorem is published. The HHKP and Bradač results are
current preprints, so deductions using them are explicitly [b], not
unconditional claims of settled literature. This version detail matters:
search indexes still expose the weaker title and theorem from Bradač v1, while
the downloaded 2026-06-16 v3 states the stronger bound displayed above.
I searched the exact consecutive-gap and ratio formulations, the cited 1989
paper, and current arXiv off-diagonal results. I found no primary source
claiming either pointwise assertion for every sufficiently large \(n\). That is
a report of the search, not a proof that no such source exists.
1. A fixed-window transfer lemma
Lemma [a]. For every \(n\geq2\) and \(h\geq1\),
\[ \boxed{R(n+h)-R(n)\ \geq\ r(h+1,n+h)-1.}\tag{T} \]Proof. First prove the more general blue-join inequality. If
\(1\leq h\leq t-2\), take
- an \((m,t-h)\)-good coloring on \(r(m,t-h)-1\) vertices, and
- an \((m,h+1)\)-good coloring on \(r(m,h+1)-1\) vertices,
and color every edge between the two parts blue. A red \(K_m\) would have to
lie in one part, where none exists. A blue clique uses at most \(t-h-1\)
vertices of the first part and at most \(h\) of the second, hence at most
\(t-1\) vertices. Therefore
\[ r(m,t)\geq r(m,t-h)+r(m,h+1)-1. \tag{1} \]Now put \(m=t=n+h\). Monotonicity and symmetry give
\[ r(n+h,n)\geq r(n,n)=R(n),\qquad r(n+h,h+1)=r(h+1,n+h). \]Substitution in (1) proves (T). \(\square\)
This is the construction in BEFS Theorem 2, reproduced here so that (T) does
not depend on a black box.
A small strengthening of the page's linear bound
BEFS Theorem 1 states
\[ r(m,t)\geq r(m,t-1)+2m-3. \]Applying it at \((m,t)=(n+1,n+1)\), then using symmetry and applying it at
\((m,t)=(n,n+1)\), gives [b]
\[ \begin{aligned} R(n+1) &\geq r(n+1,n)+(2n-1)\\ &=r(n,n+1)+(2n-1)\\ &\geq R(n)+(2n-3)+(2n-1). \end{aligned} \]Thus the cited theorem actually yields
\[ \boxed{\Delta_n\geq4n-4\quad(n\geq2),}\tag{2} \]which is four larger than, and therefore implies, the live page's displayed
\(4n-8\) bound. The verifier checks the indexing arithmetic for
\(2\leq n\leq100\); the displayed algebra proves it for all \(n\).
2. Large gaps occur in every three consecutive positions
Since
\[ R(n+h)-R(n)=\sum_{i=0}^{h-1}\Delta_{n+i}, \]the transfer lemma converts any fixed off-diagonal lower bound into a lower
bound for a short sum of consecutive diagonal gaps.
First, HHKP Theorem 1.2 and (T) with \(h=2\) give [b, current preprint]
\[ \boxed{\Delta_n+\Delta_{n+1} \geq\left(\frac12+o(1)\right)\frac{n^2}{\log n}.}\tag{3} \]This is a quantitative current version of the \(n^{2-o(1)}\) two-step result
reported on the live page. It is still a factor of order \(\log n\) short of
forcing either individual gap to be \(\gg n^2\).
More decisively, the published Mattheus–Verstraëte theorem and (T) with \(h=3\)
give [b, published theorem]
\[ \Delta_n+\Delta_{n+1}+\Delta_{n+2} \geq c\,\frac{n^3}{\log^4 n} \tag{4} \]for an absolute \(c>0\) and all sufficiently large \(n\). Hence one of these
three terms is at least one third of the right-hand side. Since
\(x^3/\log^4x\) is eventually increasing, constants can be adjusted to obtain
a \(C>0\) such that
\[ S=\left\{m:\Delta_m\geq C\frac{m^3}{\log^4m}\right\} \]meets every interval \(\{n,n+1,n+2\}\) for all sufficiently large \(n\).
Consequently [b]:
1. \(S\) is 3-syndetic: successive elements are at most 3 apart;
2. its lower natural density is at least \(1/3\), by partitioning the integers
into disjoint blocks of length 3;
3. along \(S\),
\[ \frac{\Delta_m}{m^2}\geq C\frac{m}{\log^4m}\longrightarrow\infty. \]
Thus the second conjecture is true, in a substantially stronger form, at least
once in every three consecutive indices. This does not establish it at
each index.
Current preprint hierarchy
Bradač v3 gives, for every fixed \(s\geq3\), a constant \(c_s>0\) with
\[ r(s,k)\geq c_s\frac{k^{s-1}}{(\log k)^{2s-4}}. \]Putting \(s=p+1\) and \(h=p\) in (T) yields [b, current preprint], for each
fixed integer \(p\geq2\),
\[ \sum_{i=0}^{p-1}\Delta_{n+i} \geq C_p\frac{n^p}{(\log n)^{2p-2}}. \tag{5} \]Therefore there is a \(p\)-syndetic set \(S_p\), of lower density at least
\(1/p\), on which
\[ \Delta_m\geq C'_p\frac{m^p}{(\log m)^{2p-2}}. \tag{6} \]In particular, for every fixed \(A>0\), choosing an integer \(p>A\) gives a
bounded-gap set \(S_p\) on which \(\Delta_m\geq m^A\) eventually.
The quantifiers are essential: \(p\) is fixed before \(n\to\infty\), the
constant depends on \(p\), and the set \(S_p\) also depends on \(p\). Nothing
here permits \(p=p(n)\), so (5) is not an exponential pointwise bound and does
not close either question.
3. What can be proved for the ratios without unproved machinery
The standard elementary bounds suffice to locate frequent ratio jumps.
The Ramsey recursion gives [a]
\[ R(k)\leq {2k-2\choose k-1}\leq4^{k-1}. \tag{7} \]For completeness, the first inequality follows by induction from
\(r(a,b)\leq r(a-1,b)+r(a,b-1)\), and the second because the central binomial
coefficient is one term in the expansion of \(2^{2k-2}\).
For the lower bound, color \(K_N\) randomly, where
\(N=\lfloor2^{k/2}\rfloor\). The expected number of monochromatic \(K_k\)'s is
\[ {N\choose k}2^{1-\binom{k}{2}} \leq \frac{2^{1+k/2}}{k!}<1\qquad(k\geq4). \]The final inequality holds at \(k=4\) and then inducts because the factorial
side gains a factor \(k+1>\sqrt2\). Hence some coloring has no monochromatic
\(K_k\), and [a]
\[ R(k)>\lfloor2^{k/2}\rfloor. \tag{8} \]If \(\limsup q_n<\sqrt2\), then for some \(\rho<\sqrt2\) all sufficiently large
\(q_n\leq\rho\); telescoping would give \(R(k)=O(\rho^k)\), contradicting (8).
Therefore [a]
\[ \boxed{\limsup_{n\to\infty}\frac{R(n+1)}{R(n)}\geq\sqrt2.}\tag{9} \]There is also an explicit bounded-multiplicative-waiting statement. For every
integer \(x\geq2\), (7)–(8) give
\[ \prod_{j=x}^{6x-1}q_j =\frac{R(6x)}{R(x)} >\frac{2^{3x}}{4^{x-1}}=2^{x+2}. \]But \(1.1^5=1.61051<2\). If all \(5x\) ratios in that product were below
\(1.1\), their product would be below \(1.1^{5x}<2^x\), a contradiction.
Thus [a]
\[ \boxed{\text{every }[x,6x)\text{ contains a }j\text{ with }q_j\geq1.1.}\tag{10} \]More generally, for every \(0 large that
\(j\) with \(q_j\geq1+c\). This is much weaker than “for all large \(j\)”:
the waiting interval is multiplicative, not a bounded additive interval.
4. Reproducible exact computation
The standalone script is runs/erdos812_wave6m_verify.py. It uses no external
SAT package. It builds the clique-avoidance CNF, solves it with an in-file
deterministic DPLL implementation, and independently enumerates every
potential forbidden clique in each returned coloring.
The complete run took 1.93 seconds on this VM and printed:
source snapshots: 4 PDF hashes and theorem anchors passed
r(3,3) test at N=5: SAT; DPLL nodes=6
r(3,3) test at N=6: UNSAT; DPLL nodes=55
r(3,4) test at N=8: SAT; DPLL nodes=17
r(3,4) test at N=9: UNSAT; DPLL nodes=28119
exact consequences: r(3,3)=6 and r(3,4)=9
Paley-17: checked all 2*C(17,4)=4,760 color/subset cases; R(4)>=18
blue join: checked a 13-vertex (3,6)-good coloring; r(3,6)>=14
arithmetic: random-coloring, 4n-4, and [x,6x) ratio checks passed
surrogate wall: global/window bounds coexist with linear odd gaps and q_odd->1
ALL ERDOS #812 REVERIFICATION CHECKS PASSED
Accordingly, the following finite statements are [d]:
| checked object | exhaustive result |
|---|---|
| \((3,3)\)-good colorings | exist on 5 vertices, none on 6; \(r(3,3)=6\) |
| \((3,4)\)-good colorings | exist on 8 vertices, none on 9; \(r(3,4)=9\) |
| Paley coloring on \(\mathbb Z/17\mathbb Z\), red differences \(\{1,2,4,8,9,13,15,16\}\) | no red or blue \(K_4\); \(R(4)\geq18\) |
| blue join of the 8-vertex \((3,4)\)-good witness and 5-vertex \((3,3)\)-good witness | no red \(K_3\) and no blue \(K_6\); \(r(3,6)\geq14\) |
The last object is a concrete from-scratch check of the construction behind
(1). The UNSAT conclusions are computational, not silently promoted to a
hand proof.
5. Exact remaining wall
The obstruction is local concentration, not a missing off-diagonal exponent.
Equations (4)–(6) lower-bound a sum over a short window; they do not control
how that sum is distributed among its terms.
This logical gap can be demonstrated rigorously [a] by a surrogate sequence
(not claimed to be a Ramsey sequence). Set \(A(2)=2\) and
\[ A(n+1)-A(n)=d_n,\qquad d_n=\begin{cases} 2^n,&n\text{ even},\\ 4n,&n\text{ odd}. \end{cases} \]It has all of the following features:
- \(d_n\geq4n-4\);
- \(2^{n/2}
- every window of any fixed length \(p\geq2\) contains an even index, so its
gap sum is at least \(2^n\), which eventually dominates every right-hand
side in (3)–(6);
- large ratio jumps occur at bounded intervals;
- nevertheless \(d_n=4n=o(n^2)\) at every odd \(n\), and
\(A(n+1)/A(n)=1+4n/A(n)\to1\) through odd \(n\).
The verifier checks these assertions through \(n=120\); the parity argument
and exponential-versus-polynomial comparison prove their asymptotic versions.
Thus the machinery proved here is logically compatible with failure of both
pointwise conjectures.
A sufficient new lemma for the second question would be a local
anti-concentration estimate such as
\[ \max_{0\leq i\leq2}\Delta_{n+i} \ \leq\ O\!\left(\frac{n}{\log^4n}\right) \min_{0\leq i\leq2}\Delta_{n+i}. \tag{11} \]Combined with (4), (11) would force every term in the window to be
\(\gg n^2\). No such comparison is supplied by Ramsey monotonicity, the BEFS
join, or the cited off-diagonal theorems. Equation (11) is [c], a precise
sufficient missing lemma, not a claim that it is known or optimally formulated.
For the ratio question, (7)–(10) control only long products. What is missing is
an additive-scale regularity theorem preventing exponential growth from being
stored in occasional jumps. Finite Ramsey computation cannot supply either
uniformity statement. For scale, the next raw \((4,4)\) UNSAT instance already
has 153 variables and 6,120 clique clauses; a naive exploratory solver did not
finish within the two-CPU-minute cap, so it was stopped. The \(n=43\)
\((5,5)\) CNF has 903 variables and 1,925,196 raw clique clauses. Running such
an exhaustive project would still prove only a finite Ramsey value, not either
asymptotic assertion, so no heavier computation is needed or justified for the
present goal.
PARTIAL: Proved the fixed-window transfer \(R(n+h)-R(n)\geq r(h+1,n+h)-1\); with the published \(r(4,t)\) bound, superquadratic gaps occur in every three consecutive positions (lower density at least \(1/3\)), while the supplied from-scratch checker verifies all finite certificates, but no argument forces either conjecture at every sufficiently large index.