Erdős problem #544 — wave5y report

Date: 2026-07-26 UTC

Outcome

The problem remains open. I obtained three reproducible finite/structural results:

1. An explicit 27-vertex triangle-free graph whose prefixes are Ramsey-critical

for \(R(3,k)\), simultaneously for \(2\leq k\leq 8\).

1. An exact computation in the unique \(35\)-vertex

\(R(3,9)\)-critical graph: its hypergraph of independent \(8\)-sets has transversal number exactly \(9\). Consequently its largest induced subgraph with independence number at most \(7\) has order \(26\), not \(27\). Thus the nested-critical-graph construction in item 1 provably cannot continue across the known gap \(R(3,9)-R(3,8)=8\).

1. A sharp elementary barrier for the usual one-interface vertex-replacement

construction: if the proof uses no information about the base graph beyond the two universal independence bounds, its net gain is at most \(3\), and a \(P_4\) gadget attains \(3\).

The first two are exact finite computations, independently redone by the standard-library-only checker erdos544_wave5y_verify.py. They do not settle either asymptotic question.

Claim labels

I use the requested labels throughout:

• (a) elementary-rigorous: a complete non-computational argument is given.
• (b) rigorous-modulo-named-theorem: the deduction is complete once the

explicitly cited theorem is accepted.

• (c) plausible/structural-unverified: an interpretation, literature miss,

or engineering estimate, not a theorem.

• (d) computational-only: an exact finite result proved by the accompanying

exhaustive checker.

Step 0: statement and collision check

I first attempted the requested Bright Data browser route to the live page, including both www and non-www forms and the discussion-thread endpoint. Bright Data connected and passed Cloudflare, but the site's origin returned HTTP 522 (“Connection timed out”). A final retry at 2026-07-26 23:20 UTC had the same result. This was an origin failure, not a direct-datacenter block.

The most recent accessible search rendering of the live page was crawled in the preceding month, and the forum rendering was likewise crawled in the preceding month; a forum-index result was crawled three weeks before this run. Those rendered the following exact statement:

Show that\[R(3,k+1)-R(3,k)\to\infty\]as $k\to \infty$. Similarly, prove or disprove that\[R(3,k+1)-R(3,k)=o(k).\]

The same recent rendering reported all of the following:

• status: OPEN, with “This is open, and cannot be resolved with a finite

computation”;

• “Comment activity that has not yet been incorporated into the remarks:

None”;

• “There are no solutions, partial or complete, claimed in the comments”;
• Likes this problem, Interested in collaborating, `Currently working on

this problem, This problem looks difficult, This problem looks tractable, The results on this problem could be formalisable, and I am working on formalising the results on this problem`: all None;

• two comments, both from 24 April 2026:

Marcelo wrote “I think Erdos-Szekeres gives \(R(3,k+1)-R(3,k)\leq k+1\),” and Thomas Bloom replied “Aha, of course, got carried away!”;

• page last edited 24 April 2026.

Thus the available current evidence triggered neither the claimed-proof nor the current-worker stop condition. The direct-origin 522 is an important qualification: I could not obtain a fresher origin render than the recent indexed live-thread render. The current public repository snapshot was also checked as a secondary status cross-check and still lists #544 as open, but I did not use its stale per-problem YAML as the statement.

The page's incorporated remarks give only

and the consequence of problem #1014

for some \(c>0\). These are treated as ground truth but do not answer either question.

Literature audit

I searched by the exact gap expressions, the Erdős–Sós attribution, the citations on the live page, and citations forward/backward from the paper devoted specifically to this question.

1. In Erdős,

Some new problems and results in graph theory and other branches of combinatorial mathematics (1981), pp. 2–3, the local-growth questions \(r(n+1,3)-r(n,3)\to\infty\) and the expected normalized gap tending to zero appear explicitly. (primary source)

1. Burr, Erdős, Faudree, and Schelp,

On the Difference between Consecutive Ramsey Numbers, Utilitas Mathematica 35 (1989), 115–118, prove \[ R(m,n)\geq R(m,n-1)+2m-3. \] At \(m=3\), this is the still-standard pointwise lower bound \(3\). (primary source)

1. Zhu, Xu, and Radziszowski,

A Small Step Forwards on the Erdős–Sós Problem Concerning the Ramsey Numbers \(R(3,k)\) (2016), state that the best concrete pointwise bounds are still \(3\leq\Delta_s\leq s\). They record the block bounds \[ \Delta_s\geq3,\qquad \Delta_s+\Delta_{s+1}\geq7,\qquad \Delta_s+\Delta_{s+1}+\Delta_{s+2}\geq11, \] and prove \(\Delta_s/s\to0\) conditional on their Conjecture 9, the bounded downward-jump assertion \(\Delta_s-\Delta_{s+1}\leq d\). The conjecture is not used as a theorem here. (primary source)

1. Radziszowski's current

Small Ramsey Numbers, Dynamic Survey DS1.18 (2026), §2.3(e), still says that only the easy pointwise bounds are known and directs readers to the same roadblocks. It gives \[ R(3,3),\ldots,R(3,9)=6,9,14,18,23,28,36 \] and the current range \(40\leq R(3,10)\leq41\). This is the current-data source for the small values used below.

1. Goedgebeur and Radziszowski,

New Computational Upper Bounds for Ramsey Numbers \(R(3,k)\), Theorem 3, prove that the \((3,9;35)\)-graph is unique up to isomorphism. They identify it as the 8-regular cyclic graph on \(\mathbb Z/35\mathbb Z\) with circular distances \(\{1,7,11,16\}\), originally found by Kalbfleisch. (primary source)

1. [*On the Ratio of \(R(k,\ell)\) and

\(R(k,\ell+1)\)*](https://cdn.openai.com/pdf/6dc7175d-d9e7-4b8d-96b8-48fe5798cd5b/Ramsey.pdf) proves, for each fixed \(k\), \[ \frac{R(k,\ell+1)}{R(k,\ell)} \leq 1+\ell^{-c_k} \] for all sufficiently large \(\ell\). For \(k=3\) this proves a relative gap estimate, not the absolute assertion \(o(\ell)\).

Exact-title, exact-formula, citation, and 2026-survey searches found no later paper proving a pointwise lower bound tending to infinity or resolving the \(o(k)\) question. This is an honest literature-search miss, not a proof that no such paper exists. (c)

Definitions and exact initial data

Write

A \((3,k;n)\)-graph is a triangle-free \(n\)-vertex graph with independence number \(<k\). A \((3,k;r_k-1)\)-graph is called critical.

Using \(R(3,2)=3\) and the named exact results in the current survey gives:

The last entry uses only \(40\leq R(3,10)\leq41\). (b)

1. One explicit nested critical chain

Certificate

Let \(H\) be the graph on vertices \(0,\ldots,26\) with the following edges:

01 02 05 08 0-13 0-17 0-22
14 1-11 1-12 1-21
23 27 2-11 2-16 2-21 2-26
34 36 3-10 3-13 3-20 3-24
47 49 4-16 4-18 4-26
56 57 5-10 5-20 5-24 5-26
69 6-12 6-15 6-18
7-12 7-13 7-22
89 8-10 8-12 8-15 8-24 8-25
9-11 9-14 9-19 9-23
10-11 10-18 10-19 10-23
11-15 11-17 11-25
12-14 12-17
13-14 13-15 13-19 13-25
14-16 14-18 14-20
15-16 15-20 15-23
16-19 16-22 16-24
17-18 17-19 17-20 17-24
18-21 18-25
19-21 19-26
20-21 20-22
21-24
22-23 22-25
23-24 23-26
25-26

Here 01, for example, means \(\{0,1\}\); hyphens disambiguate multi-digit labels. The executable checker contains the same certificate as integer pairs, avoiding any parsing ambiguity.

The checker recomputes triangle counts, edge counts, and exact maximum independent-set sizes for each indicated prefix:

Every prefix has zero triangles. (d)

The orders are exactly

Consequently the prefixes are simultaneously critical \((3,k;r_k-1)\)-graphs for \(2\leq k\leq8\), and their successive added vertex counts realize the exact gaps

This interpretation is (b+d): the certificate properties are checked exhaustively, while criticality imports the named exact Ramsey values.

The graph was found by a SAT search, but no SAT output or solver is trusted by the verifier. Its include/exclude maximum-independent-set routine explores both possibilities for a selected vertex and prunes only when the number of remaining vertices cannot beat the incumbent.

2. The chain cannot pass from \(k=8\) to \(k=9\)

Let \(K\) be the cyclic graph on \(\mathbb Z/35\mathbb Z\), where \(i\) and \(j\) are adjacent exactly when their circular distance is in \(\{1,7,11,16\}\). Direct recomputation gives:

These are (d). The cited Goedgebeur–Radziszowski uniqueness theorem says that, up to isomorphism, this is the only critical graph for \(R(3,9)=36\). That identification is (b).

Let \(\mathcal I_8(K)\) be the hypergraph on \(V(K)\) whose hyperedges are the independent \(8\)-sets of \(K\). Deleting \(D\subseteq V(K)\) leaves an induced graph with independence number at most \(7\) if and only if \(D\) meets every member of \(\mathcal I_8(K)\). Therefore

This equivalence is (a).

Exhaustive transversal calculation

The checker first enumerates all 3360 independent \(8\)-sets. Its transversal search then:

1. uses cyclic symmetry to require vertex \(0\) in the transversal;
2. takes the first uncovered hyperedge and branches over every vertex that

could hit it;

1. greedily packs pairwise-disjoint uncovered hyperedges and prunes only if

that packing is larger than the remaining vertex budget;

1. memoizes only states already exhausted.

Every transversal must follow one of the branches in step 2, and a packing of \(p\) disjoint hyperedges needs at least \(p\) further vertices. Thus the search is exhaustive; these are not heuristic prunes. (a), for algorithm soundness

The exact outputs are:

size 8: no transversal (76,553 recursive calls)
size 9: transversal {0,1,2,12,13,16,17,28,29} (3,475 recursive calls)

The second set is also checked directly against all 3360 hyperedges. Its 26-vertex complement has exact independence number \(7\). Hence

The values in (2) are (d).

A critical \((3,8)\)-graph has 27 vertices. Equations (1)–(2), together with the uniqueness theorem, prove that no critical \((3,9;35)\)-graph contains a critical \((3,8;27)\)-graph as an induced subgraph. (b+d)

This is a sharp negative result about one tempting construction strategy, not about the asymptotic conjecture itself.

3. A sharp barrier for a one-interface replacement gadget

This section is entirely (a).

Let \(F\) be a \((3,k)\)-graph, so \(F\) is triangle-free and \(\alpha(F)\leq k-1\), and choose \(u\in V(F)\). Delete \(u\), insert a triangle-free graph \(Q\), choose an independent attachment set \(A\subseteq V(Q)\), and join every vertex of \(A\) to every old vertex in \(N_F(u)\). Add no other cross-edges. The result \(F'\) is triangle-free: \(N_F(u)\) and \(A\) are both independent.

Put

(If the second family is empty, interpret \(q=-\infty\).)

An independent set of \(F'\) either avoids \(N_F(u)\), in which case it can use all of \(Q\), or meets \(N_F(u)\), in which case it must avoid \(A\). Both alternatives can attain their separate maxima, so the exact formula is

Adding \(u\) to an independent set in \(F-N_F[u]\) gives

Suppose a construction proof uses only these worst-case bounds and wants \(\alpha(F')\leq k\), with no additional slack information about \(F,u\). Equations (3)–(4) force the generic certificate conditions

Since \(A\) is independent, (5) gives \(|A|\leq2\). Since \(\alpha(Q-A)\leq1\), \(Q-A\) is a clique; triangle-freeness gives \(|Q-A|\leq2\). Thus

The bound is attained: take the path \(0-2-3-1\) and attach its independent endpoints \(A=\{0,1\}\). It has \(\alpha(Q)=2\) and \(\alpha(Q-A)=1\), so it gains three vertices. This recovers the constant \(3\) construction behind the known lower bound.

Therefore any unbounded-gain proof in this architecture must exploit base-graph-specific slack in at least one of \(p\leq k-2\) or \(q\leq k-1\), or it must use multiple interfaces/a genuinely global construction. The argument does not rule those out.

One exact sufficient target is now isolated. For a critical \(F\) and \(u\in V(F)\), define \(L(F,u)\) as the maximum \(|Q|-1\) over triangle-free \(Q\) and independent \(A\subseteq Q\) satisfying

If one could choose a critical \(F_k\) and \(u_k\) for every sufficiently large \(k\) with \(L(F_k,u_k)\to\infty\), then the first conjecture would follow by construction. This is a sufficient strengthening, not an equivalent reformulation.

4. A clean reduction for the \(o(k)\) question

This argument is (a) and is also the starting observation used in the OpenAI ratio paper.

Let \(G\) be any critical \((3,k+1;r_{k+1}-1)\)-graph. For every \(v\in V(G)\), the graph \(G-N_G[v]\) is a \((3,k)\)-graph: an independent \(k\)-set there, together with \(v\), would be an independent \((k+1)\)-set in \(G\). Consequently

or

Here \(\delta(G)\) is minimum degree. Since every neighborhood in a triangle-free graph is independent and \(\alpha(G)\leq k\), (7) immediately gives \(d_k\leq k+1\), the bound noted in the live-page comment.

Thus a concrete sufficient lemma for the second question is:

For every sufficiently large \(k\), there exists an \(R(3,k+1)\)-critical graph \(G_k\) with \(\delta(G_k)=o(k)\).

Equation (7) would then give \(d_k=o(k)\). The cited ratio theorem instead shows that a gap which is a fixed positive fraction of \(r_{k+1}\) would force an impossibly dense critical graph; its quantitative exponent is not strong enough to yield \(\delta(G_k)=o(k)\).

5. Why global asymptotics do not supply the missing uniformity

Even an exact asymptotic formula for a monotone integer sequence would not by itself control every consecutive difference. For example, let \(f(n)=\lfloor n^2/\log n\rfloor\) for large \(n\), and recursively set

Then \(a_n\sim n^2/\log n\), but \(a_n-a_{n-1}=1\) at every power of two. Indeed the forced discrepancy is only \(O(n/\log n)=o(n^2/\log n)\), and the sequence catches up immediately afterward. (a)

The actual known statement \(R(3,k)\asymp k^2/\log k\) is weaker still. What is missing for the first question is a pointwise, uniform construction or a structural theorem about every relevant \(k\), not another coarse global bound.

6. Computation wall and realistic next finite case

The next unknown exact value is \(R(3,10)\in\{40,41\}\). A naive edge-variable CNF for a \((3,10;40)\)-graph has:

That is \(38{,}144{,}753{,}400\) literal occurrences, or \(142.100\) GiB even at an unrealistically compact raw four bytes per literal, before solver overhead. The companion script independently recomputes this arithmetic. (d), arithmetic only

The 2026 survey reports at least \(43\times10^6\) nonisomorphic \((3,10)\)-graphs already at order \(39\). A specialized lazy, symmetry-broken extension calculation is therefore required; the flat CNF is not credible. Merely processing 43 million seeds at a broad assumed rate of 10 ms–1 s per seed would cost about 120–12,000 core-hours, before deduplication and proof logging. This is explicitly an engineering estimate, not a lower bound on algorithmic cost. (c)

I did not launch that computation on this machine. The exact checks reported here finish in a few seconds.

7. Reproduction

Run from the repository root:

python runs/erdos544_wave5y_verify.py

The verifier uses only the Python standard library. It does not read network data, use a SAT solver, or trust stored independent-set lists. It rebuilds both graphs, re-enumerates the 3360 independent \(8\)-sets, performs the exact transversal searches, checks all prefix independence numbers, verifies the \(P_4\) gadget, and recomputes the CNF arithmetic.

Observed on this VM:

nested-prefix table (order, edges, alpha): [(2, 1, 1), (5, 5, 2), (8, 11, 3), (13, 26, 4), (17, 40, 5), (22, 63, 6), (27, 89, 7)]
named-theorem exact-gap arithmetic for k=2,...,8: [3, 3, 5, 4, 5, 5, 8]
one-interface generic gadget gain: exactly 3 (P4 witness)
Kalbfleisch graph: order=35 edges=140 degree=8 independent-8-sets=3360 alpha=8
transversal search: size 8 NONE (76553 DFS calls); size 9 witness [0, 1, 2, 12, 13, 16, 17, 28, 29] (3475 DFS calls)
largest induced subgraph with alpha <= 7: order=26, witness alpha=7
naive (3,10;40) CNF arithmetic: vars=780, triangle_clauses=9880, independence_clauses=847660528, raw_32bit_literal_storage=142.100 GiB
ALL CHECKS PASSED

Runtime was approximately 5.5 seconds. The checked verifier's SHA-256 is:

0846320a7103da23921c90355ae50e9efc9c872ab87eec1799eb98b2bd6a472e

Claim ledger

PARTIAL: An exact checker exhibits nested critical graphs through k=8, proves that the unique (3,9;35) graph has independent-8-set transversal number 9 so the nesting cannot continue at k=9, and proves a sharp gain-3 barrier for generic one-interface replacement gadgets; neither asymptotic question is resolved.