Erdős problem #557 — wave 6b

Accessed 2026-07-27. The standalone re-verifier is erdos557_wave6b_reverify.py, SHA-256 0109158fa4ce2e11cffc460a1324af086547f5d88651a9ff2470e8d98911ef39.

Outcome

The unrestricted additive conjecture remains open; I found neither a claimed resolution nor a counterexample. There is nevertheless a substantial exact regime and a certified finite computation.

1. All sufficiently large bounded-degree trees satisfy a stronger bound.

For every fixed number \(q\geq2\) of colours and fixed \(\Delta\), all sufficiently large \(n\)-vertex trees \(T\) with \(\Delta(T)\leq\Delta\) satisfy \[ R_q(T)\leq q(n-2)+2. \] This is an elementary averaging consequence of Pokrovskiy's exact bounded-degree Erdős–Sós theorem, arXiv:2409.15191, Theorem 1.16. Pokrovskiy explicitly records this Ramsey consequence as Problem 6.14 and the sentence following it. Classification: (b) rigorous-modulo-named-theorem.

1. The current all-tree result is the asymptotically sharp

\[ R_q(T)\leq qn+o(n), \] uniformly over all \(n\)-vertex trees for each fixed \(q\). This follows from Davoodi–Piguet–Řada–Sanhueza-Matamala, arXiv:2603.17755, Corollary 1.6. Together with stars, it says that the worst Ramsey number over all \(n\)-vertex trees is \(qn+o(n)\). Classification: (b). It does not supply the requested \(O(1)\) error.

1. Exact certified small cases. I independently recomputed \(R_3(T)\)

for every unlabelled tree on at most five vertices: \[ \begin{array}{c|rrrrrrr} T&K_2&P_3&P_4&K_{1,3}&P_5&F_5&K_{1,4}\\ \hline R_3(T)&2&5&6&8&9&9&11, \end{array} \] where \(F_5\) has edges \(01,02,03,34\). Explicit lower colourings are checked by enumerating every injection of the tree. Every upper bound has a full CNF encoding and a regenerated DRUP proof whose every addition, including the empty clause, is independently validated by a pure-Python watched-literal RUP checker. Classification: (d) computational-only as established here. These values are not claimed new: Yang and Rowlinson computed all three-colour Ramsey numbers of graphs with at most four edges in 1994.

1. Exact wall. The standard extremal reduction would be completed by an

additive-error dense tree-embedding lemma. Existing all-tree machinery has multiplicative error \(\varepsilon n\); the missing upgrade is to \(O(1)\), uniformly over tree shape. Choosing \(\varepsilon=\Theta(1/n)\) in a theorem quantified for each fixed \(\varepsilon\) is invalid. This is the precise finiteness/uniformity step that neither the new asymptotic paper nor finite SAT checks provide.

No novelty is asserted for either named-theorem deduction or the published small values. The value added here is a checked synthesis of the live post-2025 status, the explicit bounded-degree deduction, a sharp formulation of the remaining lemma, and independently reproducible certificates.

Step 0: authoritative live-page audit

I fetched the Cloudflare-protected live page and its discussion thread through the Bright Data browser path before doing any mathematics.

The stop condition did not trigger:

• live badge: OPEN;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• all other interest/work markers displayed None.

The page says it was last edited 2026-02-08. It warns that its open status is the owner's current belief and may omit literature.

Verbatim live statement

The following is copied from the live page's own LaTeX-source view, with no word changes:

Let \(R_k(G)\) denote the minimal \(m\) such that if the edges of \(K_m\) are \(k\)-coloured then there is a monochromatic copy of \(G\). Is it true that \[ > R_k(T)\leq kn+O(1) > \] for any tree \(T\) on \(n\) vertices?

The listed notes say:

• this is a problem of Erdős and Graham, cited as

\([{\rm ErGr75},p.516]\);

• it is implied by problem #548, the Erdős–Sós conjecture;
• stars show the scale is best possible:

\(R_k(S_n)\geq kn-O(k)\) for \(S_n=K_{1,n-1}\);

• it is problem #26 in the Ramsey Theory graph-problem collection.

All five live comments

The discussion thread contained exactly five comments, newest first.

1. SamKorsky, 2026-07-21 03:55. Corollary 1.6 of

arXiv:2603.17755 “almost” implies the bound, giving \(kn+o(n)\), and may merit addition to the page notes.

1. LouisD, 2025-10-29 19:48. Suggested the one-sided

\(R(T;k)\leq kn+O(1)\) wording. The comment cites the sufficiently-large three-colour path formula and the Burr–Roberts exact star result. It is marked as addressed by a site update.

1. LouisD, 2025-10-29 20:08. Clarified that the intended \(O(1)\)

means an upper constant, possibly depending on the number of colours, rather than a two-sided asymptotic equality, and noted that Erdős and Graham wrote \(R(T;k)<kn+O(1)\).

1. Thomas Bloom, 2025-10-31 07:50. Asked for the precise

Erdős–Graham source and said the copied \([{\rm Er81c}]\) reference could not be found there.

1. LouisD, 2025-10-31 10:50. Identified the source as

On Partition Theorems for Finite Graphs, p. 516, and explained the 1973-at-head versus 1975-publication-date discrepancy.

The site explicitly says comments are user-supplied and unverified. All substantive claims used below were therefore checked against primary texts or proved again.

I use \(q\) for the number of colours below, reserving \(d\) for the number of tree edges. The natural quantification is: \(q\) is fixed, and the \(O(1)\) may depend on \(q\) but must be uniform in \(n\) and in the choice of \(n\)-vertex tree.

Primary-source and current-status audit

Original source

Erdős and Graham, On Partition Theorems for Finite Graphs, Colloquia Mathematica Societatis János Bolyai 10 (1975), pp. 515–527, define \(T_d\) to be a tree with \(d\) edges. On p. 516 they prove

and write that the Erdős–Sós conjecture would replace this by

The PDF exists and its page says exactly this; the problem is not being reconstructed from a secondary citation.

Pre-2026 general bound

Gyárfás and Tuza, An Upper Bound on the Ramsey Number of Trees, Discrete Mathematics 66 (1987), 309–310, prove for a \(d\)-edge tree

For the live page's \(n\)-vertex convention this is

This improved the original coefficient but did not approach \(q\) for fixed \(q\).

Exact two-colour case for large trees

Yi Zhao, Proof of the \((n/2-n/2-n/2)\) Conjecture for Large \(n\), Electronic Journal of Combinatorics 18 (2011), P27, states as Corollary 2.2 that every sufficiently large \(n\)-vertex tree satisfies

Thus the live problem is already known for \(q=2\).

Exact bounded-degree Erdős–Sós theorem

Pokrovskiy, Hyperstability in the Erdős–Sós Conjecture, arXiv:2409.15191v1, states:

Theorem 1.16. Let \(\Delta^{-1}\gg d^{-1}\). Let \(G\) be an \(N\)-vertex graph with \(e(G)>(d-1)N/2\). Then \(G\) contains a copy of every \(d\)-edge tree \(T\) having \(\Delta(T)\leq\Delta\).

The companion preprint Notes on embedding trees in graphs with \(O(|T|)\)-sized covers contains the stability and extremal ingredients cited in that proof. Section 6 of the first paper explicitly restates the Erdős–Graham Ramsey question as Problem 6.14 and says: “Using Theorem 1.16 we get a proof of this being true for bounded degree trees.” Both arXiv records exist, each is still v1, and the quoted theorem and application occur in the PDFs.

March 2026 all-tree asymptotic

Davoodi, Piguet, Řada, and Sanhueza-Matamala, The asymptotic version of the Erdős–Sós conjecture and beyond, arXiv:2603.17755v1 (submitted 2026-03-18), is a 104-page preprint. Its Corollary 1.6 is:

for fixed \(q,\varepsilon>0\), once the sum of the tree orders is sufficiently large. I also checked its short proof in §3.3; this is not an inference from the abstract.

Taking \(T_1=\cdots=T_q=T\) gives, uniformly over all \(n\)-vertex trees,

Equivalently, \(R_q(T)\leq qn+o(n)\).

Small values and search misses

The current Small Ramsey Numbers survey, revision 18, 2026-04-24 records \(R_3(P_3)=5\), \(R_3(P_4)=6\), and \(R_3(P_5)=9\), and says Yang and Rowlinson determined \(R_3(G)\) for every graph \(G\) with at most four edges and no isolated vertices. The primary paper is The Third Ramsey Numbers for Graphs with at Most Four Edges90182-1), Discrete Mathematics 125 (1994), 399–406.

I searched the current survey, the cited primary papers, arXiv, journal records, and queries for the exact Erdős–Graham formulation. I found no post-2025 full proof or falsification. The March 2026 asymptotic paper and the bounded-degree preprints above were the only directly stronger current developments found. A search miss is not a proof of nonexistence, so the claim here is only that no further usable source was located.

Result 1: the bounded-degree regime

Proposition. Fix \(q\geq2\) and \(\Delta\). For all sufficiently large \(n\), if \(T\) is an \(n\)-vertex tree with \(\Delta(T)\leq\Delta\), then

Proof. Put

In any \(q\)-edge-colouring of \(K_N\), some colour graph \(G\) has

Since \(N-1=q(n-2)+1\),

The tree \(T\) has \(d=n-1\) edges, so \((d-1)N/2=(n-2)N/2\). Pokrovskiy's Theorem 1.16 therefore embeds \(T\) in \(G\), monochromatically. \(\square\)

Relative to the live target this is

so it supplies an explicit additive constant. The only non-elementary input is the named preprint theorem. Classification: (b).

Result 2: the exact extremal reduction and the missing lemma

For a graph \(T\), let \(\operatorname{ex}(N,T)\) be the maximum number of edges in an \(N\)-vertex \(T\)-free graph. Pure averaging gives the exact sufficient condition

Indeed, the largest colour class has at least \(\binom N2/q\) edges. This is the entire reason problem #548 implies #557.

If the full Erdős–Sós bound

held for every \(n\)-vertex tree, substituting \(N=q(n-2)+2\) into (1) would prove

The bounded-degree result above is exactly this argument in the regime where (2) is available.

There is a useful weaker target. At the desired order \(N=qn+C\), the densest colour has average degree at least

Consequently the live problem would follow from the following restricted additive embedding lemma:

For every fixed \(q\), there is a constant \(A_q\) such that every graph on \(qn+O_q(1)\) vertices with average degree greater than \(n+A_q\) contains every \(n\)-vertex tree.

This is weaker than the full Erdős–Sós conjecture, whose threshold is \(n-2\), and it is required only for host/tree order ratio near \(q\). Nevertheless, it is not supplied by current all-tree results.

Corollary 1.4 of arXiv:2603.17755 requires average degree more than \((1+\varepsilon)(n-1)\), for every fixed \(\varepsilon>0\). Its error is \(\Theta(\varepsilon n)\). The implication

does not permit setting \(\varepsilon=1/n\). Regularity-based \(n_0\)'s are in any event enormous and non-uniform as \(\varepsilon\to0\). Thus the exact missing step is an additive-error, all-tree embedding theorem at fixed host density. The reduction is (a) elementary-rigorous; the assessment that no such theorem was found is an honest literature-search wall.

No feasible finite computation closes this gap: the asymptotic theorem does not provide a manageable explicit cutoff below which cases could be checked. A direct CNF with one forbidden clause per labelled copy has \(\Theta(qN^2)\) variables/colour constraints but up to

tree-copy clauses. At \(N\sim qn\) this is superexponential in \(n\). Lazy generation helps tiny instances but does not replace the uniform embedding lemma.

Result 3: exact stars, from scratch

The page gives only the scale \(qn-O(q)\). The exact result is

This is the diagonal specialization of Burr–Roberts (1973), but the following proof is self-contained.

Put \(d=n-2\). A colouring avoids \(S_n\) exactly when every vertex has degree at most \(d\) in every colour. Hence any avoiding colouring of \(K_M\) must satisfy

At the equality order \(M=qd+1\), every vertex would have degree exactly \(d\) in every colour. Thus every colour graph would be \(d\)-regular.

• If \(q\) is even and \(n\) is odd, then both \(M=qd+1\) and

\(d=n-2\) are odd. A \(d\)-regular graph on odd order is impossible by the handshaking lemma. On the other hand, \(K_{qd}\) has a 1-factorisation; grouping its \(qd-1\) perfect matchings into \(q\) groups of sizes at most \(d\) gives an avoiding colouring. Therefore \(R_q(S_n)=qd+1\).

• Otherwise, if \(d\) is even, \(M\) is odd and a 2-factorisation of

\(K_M\), grouped \(d/2\) factors per colour, gives an avoiding colouring. If \(d\) is odd, the nonexceptional case forces \(q\) odd, so \(M\) is even; a 1-factorisation grouped \(d\) factors per colour does the same. Thus \(K_{qd+1}\) is avoidable, while (6) rules out \(K_{qd+2}\), giving \(R_q(S_n)=qd+2\).

This also shows directly why the conjectured leading coefficient \(q\) cannot be lowered for all trees. Classification: (a) elementary-rigorous. The verifier checks the parity arithmetic for \(2\leq q,n\leq100\) as a guard against indexing mistakes; the proof, not that finite check, establishes (5).

Result 4: certified \(q=3,\ n\leq5\) table

Complete census

There are \(1,1,2,3\) unlabelled trees on \(2,3,4,5\) vertices. The verifier does not assume these counts: it exhausts every \((n-1)\)-edge subgraph of \(K_n\), keeps the connected ones, canonically relabels them by trying all \(n!\) permutations, and confirms that the hard-coded cases are exactly the resulting isomorphism types.

The exact results and upper certificates are:

Explicit nontrivial lower witness

One colouring of \(K_8\) simultaneously avoids \(P_5\) and \(F_5\). On vertices \(0,\ldots,7\), its colour classes are

They partition all \(28\) edges. The verifier tests every injection of each tree into each colour graph; neither tree occurs. Hence

All other lower witnesses, including colourings of \(K_4,K_5,K_7\), and \(K_{10}\), are explicit edge lists in the standalone file and are checked the same way.

Full upper encoding

For each edge \(e\in E(K_m)\) and colour \(c\in\{0,1,2\}\), the CNF has a variable \(x_{e,c}\). It contains:

1. exactly-one-colour clauses for every edge;
2. for every injective copy \(\phi:T\hookrightarrow K_m\) and every colour

\(c\), the clause \[ \bigvee_{uv\in E(T)}\neg x_{\phi(u)\phi(v),c}; \]

1. the safe symmetry break \(x_{01,0}\), since colours can always be renamed.

Thus the CNF is satisfiable exactly when \(K_m\) has a three-colouring with no monochromatic \(T\). Duplicate edge-set copies are removed, but no isomorphism or sampling assumption is made.

Glucose 4.2 generates a DRUP trace for each claimed-unsatisfiable upper instance. The script then discards the solver verdict and checks the trace: an added clause \(C\) is accepted only when unit propagation from the current formula plus \(\{\neg\ell:\ell\in C\}\) reaches a conflict. The checker is a separate pure-Python watched-literal implementation. Deletion records can soundly be ignored, because retaining already proved clauses only strengthens the formula. The final empty clause is explicitly required and checked.

This establishes each upper value computationally, rather than trusting an opaque UNSAT string. It is still labelled (d), not promoted to an elementary theorem.

Reproduction

Run:

python runs/erdos557_wave6b_reverify.py

The final clean run took 11.9 wall-seconds and printed:

Checking the exact R_3(T) table for every tree with 2 <= |T| <= 5
Unlabelled-tree census PASS (counts 1, 1, 2, 3)
K2: R_3=2 (the sole edge is monochromatic)
P3   : R_3= 5; K_4 witness PASS; K_5 UNSAT PASS (30 tree copies, 131 base clauses, 3 checked RUP additions, 0.00s)
P4   : R_3= 6; K_5 witness PASS; K_6 UNSAT PASS (180 tree copies, 601 base clauses, 85 checked RUP additions, 0.01s)
K1,3 : R_3= 8; K_7 witness PASS; K_8 UNSAT PASS (280 tree copies, 953 base clauses, 105 checked RUP additions, 0.01s)
P5   : R_3= 9; K_8 witness PASS; K_9 UNSAT PASS (7560 tree copies, 22825 base clauses, 5033 checked RUP additions, 6.30s)
fork5: R_3= 9; K_8 witness PASS; K_9 UNSAT PASS (7560 tree copies, 22825 base clauses, 4762 checked RUP additions, 4.87s)
K1,4 : R_3=11; K_10 witness PASS; K_11 UNSAT PASS (2310 tree copies, 7151 base clauses, 2161 checked RUP additions, 0.49s)
ALL CHECKS PASSED (11.67s in certified upper solves)

Claim ledger

• Live statement, status, comments, and markers: direct Bright Data page

extraction on 2026-07-27.

• Exact star formula (5): (a) elementary-rigorous; also matches the

named Burr–Roberts theorem.

• Extremal reduction (1)–(4): (a) elementary-rigorous.
• Bounded-degree bound \(R_q(T)\leq q(n-2)+2\): **(b)

rigorous-modulo-Pokrovskiy Theorem 1.16**.

• Uniform all-tree bound \(R_q(T)\leq qn+o(n)\): **(b)

rigorous-modulo-Davoodi et al. Corollary 1.6**.

• Exact \(R_3(T)\) table through five vertices: **(d) computational-only in

this report**, with explicit witnesses and checked RUP refutations.

• Claim that the additive all-tree step is presently missing:

literature-search diagnosis, not a theorem and not a priority claim.

PARTIAL: verified \(R_q(T)\leq q(n-2)+2\) for all sufficiently large fixed-bounded-degree trees (modulo Pokrovskiy Theorem 1.16), certified every \(R_3(T)\) for \(|T|\leq5\), and isolated the unresolved all-tree step as an additive-error embedding lemma beyond the current \(qn+o(n)\) theorem.