Erdoes #812 - working report - Erdős Problem a Day

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]:

\(S\) is 3-syndetic: successive elements are at most 3 apart;
its lower natural density is at least \(1/3\), by partitioning the integers

into disjoint blocks of length 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<c<\sqrt2-1\), choose a fixed integer \(L\) so large that

(L-1)\log_2(1+c)<L/2-2.

The same calculation shows that every sufficiently large \([x,Lx)\) contains \(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}<A(n)\leq4^{n-1}\) for all sufficiently large \(n\);
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.

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