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\).

2. 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\).

3. 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)](https://users.renyi.hu/~p_erdos/1981-32.pdf),

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)

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

[On the Difference between Consecutive Ramsey Numbers,

Utilitas Mathematica 35 (1989), 115–118](https://combinatorica.hu/~p_erdos/1989-21.pdf),

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)

3. Zhu, Xu, and Radziszowski,

[*A Small Step Forwards on the Erdős–Sós Problem Concerning the Ramsey

Numbers \(R(3,k)\)* (2016)](https://www.cs.rit.edu/~spr/PUBL/r3k15.pdf),

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)

4. Radziszowski's current

[Small Ramsey Numbers, Dynamic Survey DS1.18

(2026)](https://www.cs.rit.edu/~spr/ElJC/ejcram18.pdf), §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.

5. Goedgebeur and Radziszowski,

[*New Computational Upper Bounds for Ramsey Numbers

\(R(3,k)\)*](https://arxiv.org/abs/1210.5826), 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)

6. [*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 \(

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

| \(k\) | \(r_k\) | \(d_k=r_{k+1}-r_k\) |

|---:|---:|---:|

| 2 | 3 | 3 |

| 3 | 6 | 3 |

| 4 | 9 | 5 |

| 5 | 14 | 4 |

| 6 | 18 | 5 |

| 7 | 23 | 5 |

| 8 | 28 | 8 |

| 9 | 36 | \(4\) or \(5\) |

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:

| prefix order | edges | exact \(\alpha\) |

|---:|---:|---:|

| 2 | 1 | 1 |

| 5 | 5 | 2 |

| 8 | 11 | 3 |

| 13 | 26 | 4 |

| 17 | 40 | 5 |

| 22 | 63 | 6 |

| 27 | 89 | 7 |

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:

| property | recomputed value |

|---|---:|

| vertices | 35 |

| edges | 140 |

| degree of every vertex | 8 |

| triangles | 0 |

| independent \(8\)-sets | 3360 |

| independent \(9\)-sets | 0 |

| \(\alpha(K)\) | 8 |

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;

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

that packing is larger than the remaining vertex budget;

4. 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

| Claim | Status |

|---|---|

| Exact live statement/status as rendered by the recent page index | provenance-qualified; direct origin was HTTP 522 |

| Prefix graph table and nested certificate | (d) |

| Prefixes are critical for \(2\leq k\leq8\) | (b+d) |

| Kalbfleisch graph has \(\alpha=8\) and 3360 independent \(8\)-sets | (d) |

| Its independent-\(8\)-set transversal number is \(9\) | (d) |

| No \(R(3,9)\)-critical graph contains an induced \(R(3,8)\)-critical graph | (b+d) |

| Exact one-interface independence formula and sharp gain-\(3\) barrier | (a) |

| Critical-graph minimum-degree reduction (7) | (a) |

| No later solution found in the searched literature | (c) |

| The two asymptotic questions are resolved here | not claimed |

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.