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<R(4)=18\), where \(W_6=K_1\vee C_5\);
• 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\).

1. 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:

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

\(43\le R(5)\le46\)

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

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

\(R(K_5-e)=22\)

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

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

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

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

Optimizing the CGMS Upper Bound on Ramsey Numbers, arXiv:2407.19026.

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

112 (2026), 198--208, DOI.

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

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