Erdős problem 87 — wave 5h

Date checked: 2026-07-26 (UTC)

Result in one paragraph

The problem remains open. I obtained three verifiable partial results. First, every

graph \(G\) with \(\chi(G)=k\) satisfies

Combining (1) with the current diagonal upper bound of Gupta--Ndiaye--Norin--Wei

proves the first question for every fixed

Second, deciding a proposed universal lower bound \(R(G)\ge T\) at fixed

chromatic number \(k\) reduces to the finitely many connected edge-\(k\)-critical

graphs on at most \(\lceil(T-1)/(k-1)\rceil\) vertices. For \(k=5,T=43\), the

published catalogue has only 4,195 such graphs, all on at most 11 vertices; I

independently checked the criticality of every record. Third, I found and

certified a 25-vertex coloring with no monochromatic

\(K_2\mathbin{\vee}C_5\), proving

\(R(K_2\mathbin{\vee}C_5)\ge26\). None of these closes either asymptotic

question.

Claim labels used below:

• (a) elementary-rigorous: a complete proof or a finite certificate checked

from first principles is included.

• (b) rigorous-modulo-named-theorem: the deduction is rigorous, conditional

only on an explicitly named published/preprint theorem.

• (c) plausible/structural-unverified: interpretation, search assessment, or

an explicitly non-proved possibility.

• (d) computational-only: an exhaustive calculation or data observation,

with no claim that it is a human proof.

Step 0: live-page collision and statement check

(d) I fetched the live page through the Bright Data browser path at

erdosproblems.com/87; ordinary datacenter

fetching returned the expected Cloudflare 403. The live page showed:

• status: OPEN;
• last edited: 17 January 2026;
• comments: 0;
• claimed proofs: 0;
• interested in collaborating: None;
• currently working: None.

Thus the mandatory stop condition did not apply.

The first paragraph of the live statement is:

> Let \(\epsilon >0\). Is it true that, if \(k\) is sufficiently large, then

> \[R(G)>(1-\epsilon)^kR(k)\]

> for every graph \(G\) with chromatic number \(\chi(G)=k\)?

The second displayed inequality on the page is exactly

and asks the stronger question whether some fixed \(c>0\) makes this true for

every \(k\)-chromatic \(G\) once \(k\) is large.

(b) The live page also records the following known information:

• the source is Erdős, *Some of my Favourite Problems in Number Theory,

Combinatorics, and Geometry*, p. 14

(paper/DOI);

• Erdős's earlier conjecture \(R(G)\ge R(k)\) is trivial at \(k=3\) but false at

\(k=4\);

• Faudree and McKay proved \(R(W_6)=17
• the page notes the elementary \(R(k)\le4^k\) observation and credits Yuval

Wigderson with the random-coloring lower bound

\(R(G)\gg2^{k/2}\).

I checked Erdős's scan at the cited page and the

Faudree--McKay primary paper,

not just the tracker summary.

Throughout, \(R(G)=R(G,G)\), and \(R(k)=R(K_k,K_k)\).

1. An explicit uniform lower bound

Theorem 1 (a)

For every graph \(G\) with \(\chi(G)=k\),

Proof

Choose an inclusion-minimal \(k\)-chromatic subgraph \(H\subseteq G\). Write

\(h=|V(H)|\) and \(m=|E(H)|\). Minimality gives all of the facts needed here:

1. \(H\) is connected.

2. Every vertex has degree at least \(k-1\). Otherwise, a

\((k-1)\)-coloring of \(H-v\) could be extended to \(v\).

3. Consequently,

\[ h\ge k,\qquad m\ge\frac{(k-1)h}{2}. \tag{3} \]

Color the edges of \(K_N\) independently and uniformly red or blue. There are

at most \(N^h\) labeled embeddings of \(H\). For any fixed embedding, the

probability that all its \(m\) edges have one color is \(2^{1-m}\). Hence

If

then, using (3), the base-2 logarithm of the right side of (4) is strictly less

than

Thus the expectation is strictly below one. Some coloring contains no

monochromatic \(H\), and therefore no monochromatic \(G\). The largest integer

strictly below the displayed real threshold is \(L_k\), proving the theorem.

The verifier recomputes the exponent identity exactly with rational arithmetic,

not floating point.

Consequence using the best diagonal upper bound located (b)

Gupta, Ndiaye, Norin and Wei, *Optimizing the CGMS upper bound on Ramsey

numbers*, arXiv:2407.19026, prove

Targeted searches through 2026-07-26 located no later improvement of this

diagonal exponential constant; current 2026 references still cite it as the

best known upper base. From (1) and (5),

Let \(p=1-\epsilon\). If \(p<\sqrt2/B\), then the ratio between the lower

bound in (6) and \(p^k\) tends exponentially to infinity; the \(o(k)\) term in

(5) cannot change that. This proves the desired strict inequality for every

fixed

The endpoint \(\epsilon=\epsilon_0\) is not claimed because the unspecified

\(o(k)\) in (5) matters there.

2. A finite reduction for every concrete target

Theorem 2 (a)

For integers \(k,T\ge2\), set

The assertion

is equivalent to checking (7) only for connected edge-\(k\)-critical graphs

\(H\) with \(|V(H)|\le s\).

Proof

Necessity is immediate. For sufficiency, take an arbitrary \(k\)-chromatic

\(G\) and an inclusion-minimal \(k\)-chromatic subgraph \(H\subseteq G\).

It is connected and edge-\(k\)-critical.

If \(|V(H)|\le s\), this is one of the finite checks. If \(|V(H)|>s\), color

the edges of \(K_{T-1}\) by partitioning its vertices as evenly as possible

into \(k-1\) classes, coloring within classes red and between classes blue.

Every red connected component has at most \(s\) vertices, so it cannot contain

the connected graph \(H\). The blue graph is \((k-1)\)-partite, so it cannot

contain the \(k\)-chromatic graph \(H\). This coloring avoids \(H\), proving

\(R(H)\ge T\), and \(H\subseteq G\) gives \(R(G)\ge R(H)\).

This reduction is exact; it is not merely a one-way heuristic.

The \(k=4\) regime (b)+(d)

For \(k=4,T=17\), the cutoff is

\(\lceil16/3\rceil=6\). A from-scratch enumeration of all labeled graphs on

4, 5, and 6 vertices found:

| order | connected edge-4-critical labeled graphs | type |

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

| 4 | 1 | \(K_4\) |

| 5 | 0 | — |

| 6 | 72 | all labelings of \(W_6=K_1\vee C_5\) |

The order-6 identification needs no isomorphism software: every result has

degree sequence \((3,3,3,3,3,5)\); deleting its universal vertex leaves a

2-regular graph on five vertices, hence \(C_5\). Combining Theorem 2 with the

published exact values \(R(K_4)=18\) and \(R(W_6)=17\) gives the sharp concrete

statement

The enumeration itself is (d); the conclusion is (b) because its upper

half uses Faudree--McKay's published exhaustive computation of \(R(W_6)=17\).

The verifier independently checks their explicit 16-vertex lower-bound

coloring, but not their entire upper-bound search. For completeness, that red

graph has vertex set

\(\{0,1\}\times\{0,\ldots,7\}\), with

\((i,j)(i',j')\) an edge exactly when

\(\lvert j-j'\rvert\in\{0,1,4,7\}\) (distinct vertices understood). The checker

tests directly that neither this graph nor its complement has a vertex whose

neighborhood contains a \(C_5\), which is exactly the condition for avoiding

\(W_6\).

The \(k=5,T=43\) reduction (a)+(d)

The 2026 result of Angeltveit and McKay gives

(R(5,5) <= 46); 43 is still the best

known lower bound, not the known exact value. For \(k=5,T=43\),

Thus proving \(R(G)\ge43\) for every 5-chromatic \(G\) requires only the

edge-5-critical cores through order 11.

Brendan McKay's

edge-critical graph catalogue

states that these files were generated by Olivier Lalonde's

gencrit. I downloaded the six nonempty

graph6 files, pinned their exact bytes by SHA-256, and independently checked

every record with an exact DSATUR backtracker. Each graph was checked to be

connected, 5-colorable, not 4-colorable, and 4-colorable after deletion of

every edge. An independent exhaustive labeled search confirms that order 6

contributes zero.

The resulting reproducible table is:

| \(n\) | count | edge-count histogram | clique-number histogram | minimum-degree histogram |

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

| 5 | 1 | 10:1 | 5:1 | 4:1 |

| 6 | 0 | — | — | — |

| 7 | 1 | 16:1 | 4:1 | 4:1 |

| 8 | 2 | 18:1, 19:1 | 4:2 | 4:2 |

| 9 | 21 | 19:2, 20:1, 21:6, 22:12 | 4:21 | 4:21 |

| 10 | 162 | 22:1, 23:2, 24:54, 25:99, 26:6 | 4:162 | 4:162 |

| 11 | 4,008 | 25:20, 26:91, 27:844, 28:2685, 29:328, 30:39, 31:1 | 3:22, 4:3986 | 4:4004, 5:4 |

| total | 4,195 | | | |

Pinned hashes:

crit_5_5.g6   04003765f09de2f4e929e50b225b2fff590e4f0b9106c3eab308682abdd60944
crit_7_5.g6   564b6437001734303ba016e840b5de717ed11ce8d5d0d921d0edea9882f03fd8
crit_8_5.g6   74504d190c9f1315a1d46854b92d4817dec4b43c62f09763e716fd5de3c83a72
crit_9_5.g6   faff60b46a1fc8ab13ec9a2b938be437da499df649c98518a93b0e67b87a61b4
crit_10_5.g6  fa8e5dededc3e94956cb005b3dc5e53631d21917e85d5fbce3e8aead26328a97
crit_11_5.g6  e9c383303affa4a53b6b4454d7becf0e7d78b4e8a685c17ef5027f6ce3f848c4

Important scope: the 4,195-record count is (d). My checker validates

every listed member, but does not independently prove that gencrit omitted no

isomorphism class or emitted no duplicate class. Catalogue completeness remains

an external computational assertion. The mathematical reduction to whatever

the complete finite list is remains (a).

Also, \(R(G)\ge43\) for all 5-chromatic \(G\), if eventually checked, would

match the best known lower bound for \(R(5)\); it would not prove

\(R(G)\ge R(5)\) unless \(R(5)=43\) were also established.

3. A new explicit certificate found in this run

Let

It has seven vertices, 16 edges, and chromatic number

\(2+3=5\). It is edge-5-critical; the verifier checks every edge deletion.

This is the unique order-7 graph in the catalogue.

Certificate (a)

The following graph6 string encodes the red graph of a coloring of \(K_{25}\);

the complement is the blue graph:

XuPorxakyNjuOe_mtNCxBLKf_fHTDvq]e~Elu\AkJYgeWgxfa^@

The red graph has 152 edges and sorted degree sequence

10,
11,11,11,11,11,11,
12,12,12,12,12,12,12,12,12,12,
13,13,13,13,
14,14,14,14

A graph contains \(K_2\vee C_5\) if and only if some adjacent pair \(u,v\)

has a 5-cycle inside \(N(u)\cap N(v)\). The standalone verifier implements its

own graph6 decoder, examines every adjacent pair, and exhaustively enumerates

all 5-cycles in the common neighborhood. It finds none in the red graph and

none in its complement. Therefore

This is a finite construction with a from-scratch checker, so (8) is

elementary-rigorous rather than merely a solver observation. The exploratory

SAT search is only the provenance of the certificate. As a separate

cross-check, NetworkX's general-purpose subgraph monomorphism routine also

returned False independently for both the 152-edge red graph and its

148-edge complement.

The graph \(H\) contains \(K_5-e\): take the two \(K_2\) vertices and three

consecutive rim vertices. Clapham, Exoo, Harborth, Mengersen and Sheehan proved

(primary DOI), so (8) improves the

lower bound inherited from that subgraph from 22 to 26.

(c) Exact-title, formula, and graph-name searches located no published

value or bound specifically for \(R(K_2\vee C_5)\) or \(R(K_7-C_5)\). This

search miss is not a novelty claim.

4. Computations attempted and the exact computational wall

SAT encoding

For each edge \(uv\) of \(K_N\), use a Boolean variable \(x_{uv}\). For every

copy \(F\) of a target graph, add

These respectively forbid an all-blue and an all-red copy. The lazy version

starts without all embedding clauses, asks for a model, finds a monochromatic

copy by the common-neighborhood cycle test, adds its violated clause, and

repeats. A satisfying assignment is independently useful only after the

standalone checker accepts it; an UNSAT claim would require a checkable proof

certificate.

What ran (d)

• The \(K_2\vee C_5\) search produced avoiding colorings successively through

\(N=25\), yielding the certificate above.

• A direct \(N=26\) probe was stopped after 20 seconds without a model or an

UNSAT proof. This says nothing about \(R(H)\le26\).

• A lazy \(N=30\) probe ran for 96 seconds and 7,600 separation iterations,

adding about 1.65 million clauses, before being stopped without either kind

of certificate.

• For comparison, I generated the complete \(W_6\) CNF at \(N=17\):

136 variables and 1,782,144 clauses. Two solver attempts, including a

degree-symmetry restriction, remained unresolved after roughly 2--2.5

minutes. Therefore I do not claim an independent verification of the

Faudree--McKay upper bound; only their explicit lower coloring is checked

here.

Why the \(k=5,T=43\) finite reduction is not yet a feasible brute-force

proof

Even for the smallest noncomplete candidate \(K_2\vee C_5\), the number of

distinct copies in the labeled host \(K_{42}\) is

Both colors therefore require 13,597,077,312 clauses of length 16. Storing only

the 32-bit literals, with no clause or solver overhead, would take

870,212,947,968 bytes (870.2 decimal GB). The full-CNF encoding is thus

inappropriate on this VM.

A merely 15-minute screening budget over all 4,195 candidates would already be

and would not constitute a proof: the smallest candidate already failed to

resolve at \(N=30\) in the short lazy probe, far below \(N=42\). A realistic

campaign needs a much stronger symmetry-aware/incremental encoding, parallel

search, and independently checked SAT certificates. Without benchmark data

from such an encoding, quoting a purported completion time would be

fabricated; the exact task that remains is 4,195 certified Ramsey decisions at

\(N=42\), or one checked counterexample.

5. Why the standard first moment stalls

(a) For \(k\ge4\), the family

is edge-\(k\)-critical. Indeed, chromatic number is additive under graph join,

so \(\chi(H_k)=(k-3)+3=k\). Deleting an edge in the clique lowers its

chromatic contribution by one; deleting a rim edge turns \(C_5\) into the

bipartite path \(P_5\). After deleting a join edge \(uv\), color the clique

vertices distinctly, let the rim vertex \(v\) reuse the color of \(u\), and

alternate two new colors on the other four rim vertices. Each deletion is

therefore \((k-1)\)-colorable, and deleting one edge can lower chromatic number

by at most one.

The family has

so

The verifier constructs this family for \(4\le k\le20\), checks its chromatic

number and every edge deletion, and recomputes (9). Thus criticality alone

cannot force average edge density \((1+\delta)k/2\) for a fixed

\(\delta>0\).

Any union bound that uses only the number \(h\) of vertices and \(m\) required

same-colored edges has threshold approximately \(N<2^{m/h}\). On (9), this is

only a constant multiple of \(2^{k/2}\). Therefore an edge-density-only

refinement cannot improve the exponential base \(\sqrt2\). This does not show

that \(R(H_k)\) itself is small; it identifies the precise limitation of that

proof method.

6. Literature audit

(b) Primary sources actually opened and checked:

1. P. Erdős, *Some of my Favourite Problems in Number Theory,

Combinatorics, and Geometry*,

DOI/source, especially

p. 14.

2. R. Faudree and B. McKay, *A Conjecture of Erdős and the Ramsey Number

\(r(W_6)\)*, JCMCC 13 (1993), 23--31

(author PDF).

3. P. Gupta, N. Ndiaye, S. Norin and L. Wei,

Optimizing the CGMS Upper Bound on Ramsey Numbers,

arXiv:2407.19026.

4. V. Angeltveit and B. McKay, \(R(5,5)\le46\), Journal of Graph Theory

112 (2026), 198--208,

DOI.

5. C. Clapham, G. Exoo, H. Harborth, I. Mengersen and J. Sheehan,

The Ramsey Number of \(K_5-e\), Journal of Graph Theory 13 (1989),

DOI.

6. McKay's critical-graph data page

and Lalonde's gencrit.

(c) Searches used the exact live-statement phrases, the citation

“Erdős 1995 p.14,” variants of “chromatic number versus diagonal Ramsey

number,” and the concrete names \(K_2\vee C_5\), \(K_7-C_5\), and

\(R(K_5-e)\). I found the original question, the wheel counterexample, diagonal

Ramsey improvements, and unrelated chromatic-Ramsey invariants, but no paper

claiming either asymptotic question here. In particular, Benny Sudakov's

similarly titled

A conjecture of Erdős on graph Ramsey numbers

proves an upper bound in terms of the number of edges; it is a different Erdős

conjecture and was not used.

7. Reproduction

The complete standalone verifier is

runs/erdos87_wave5h_verify.py. It uses only the

Python standard library. Its default mode downloads the six pinned catalogue

files and checks all 4,195 graphs; --skip-catalog performs only the offline

proof arithmetic, exhaustive small classifications, and explicit certificate

checks. Verifier SHA-256:

46af1d952d8e82b691ae6892cb70e2d1deaea0831155f70bd357e3715879edfb.

Commands:

python3 runs/erdos87_wave5h_verify.py --skip-catalog
python3 runs/erdos87_wave5h_verify.py

Observed full-run output:

asymptotic constants: B=3.799202739615937 sqrt(2)/B=0.372239561639203 epsilon_0=0.627760438360797
checked K_(k-3) join C5 for 4 <= k <= 20
finite reduction check: k=5, T=43, s=11, parts=11+11+10+10
full K42 CNF for K2 join C5: 13,597,077,312 clauses, 870.2 GB raw 32-bit literals
exhaustive check: no connected edge-5-critical graph on 6 vertices
exhaustive check: critical chi=4 cores through order 6 are K4 and W6
certificate check: 25 vertices avoid monochromatic K2 join C5
certificate check: Faudree--McKay K16 coloring avoids W6
catalog n=5: 1 graphs, sha256=04003765f09d..., validated
catalog n=7: 1 graphs, sha256=564b64370017..., validated
catalog n=8: 2 graphs, sha256=74504d190c9f..., validated
catalog n=9: 21 graphs, sha256=faff60b46a1f..., validated
catalog n=10: 162 graphs, sha256=fa8e5dededc3..., validated
catalog n=11: 4008 graphs, sha256=e9c383303aff..., validated
catalog total: 4,195 edge-5-critical records validated
ALL CHECKS PASSED

The final full rerun completed successfully in 25.24 seconds elapsed

(22.14 user-CPU seconds), with peak resident memory 24,780 KB.

8. Exact remainder

Define

Because \(K_k\) is among the graphs minimized over, \(f(k)\le R(k)\). The first

question is exactly the assertion

while the stronger question asks whether \(f(k)/R(k)\) is bounded below by a

positive constant for all sufficiently large \(k\).

What has been proved here is only

The exponential gap still left by the available machinery is

The exact missing ingredient is therefore a uniform structural lower-bound

lemma strong enough to give

or an equally strong new upper estimate on \(R(k)\). For the constant-factor

question, the \(o(k)\) loss must be improved all the way to \(O(1)\). The

low-density critical family in Section 5 proves that minimum-degree/edge-count

plus a first-moment union bound cannot supply this lemma. Finite computations

at \(k=4\) or \(5\), even if completed, do not provide the required uniformity.

PARTIAL: proved the first inequality for every epsilon > 0.627760438360797, reduced the k=5 lower bound 43 to 4,195 checked critical candidates, and certified R(K_2 join C_5) >= 26; both full asymptotic questions remain open.