Erdős problem 562 — wave 6c report

Date of live-page check and computation: 2026-07-27 UTC.

Outcome

I did not resolve the asymptotic conjecture. I obtained two verifiable outputs:

1. a self-contained, compact certificate and two independent exhaustive checks of a cyclic

red/blue coloring of the triples of 87 vertices with no monochromatic 5-set, proving the finite lower bound \(R_3(5)\geq 88\); and

1. an elementary uniform obstruction showing that the most tempting tournament-based

two-color collapse of the usual stepping-up construction always contains a monochromatic set of size \(m+1\) on its \(2^m\) vertices, so that particular construction cannot even give a double exponential lower bound.

The 87-vertex coloring is not claimed as new: it is the construction in Janusz Dybizbański's author-hosted addendum. The contribution here is a portable 609-orbit encoding, a standard-library verifier, an independent direct check of all \(\binom{87}{5}=36,949,857\) five-sets, and a precise audit of the next cyclic SAT instance.

Claim labels used below are exactly those requested:

• (a) elementary-rigorous;
• (b) rigorous modulo the explicitly named theorem;
• (c) plausible/structural-unverified;
• (d) computational-only.

Step 0: authoritative live-page gate

I fetched the live problem page and its LaTeX view through the Bright Data browser path, not datacenter curl.

Live-page observations:

Thus the mandatory stop condition did not fire.

The page defines \(R_r(n)\) to be the least \(m\) for which every two-coloring of the \(r\)-subsets of an \(m\)-element set has an \(n\)-element subset whose \(r\)-subsets all have one color. Its exact formula-bearing request is:

“Prove that, for \(r\geq 3\), \(\log_{r-1}R_r(n)\asymp_r n\), where \(\log_{r-1}\) denotes the \((r-1)\)-fold iterated logarithm. That is, does \(R_r(n)\) grow like \(2^{2^{\cdots n}}\) where the tower of exponentials has height \(r-1\)?”

The only result note on the page attributes the problem to Erdős, Hajnal, and Rado ([EHR65]) and calls it a generalization of problem 564. It is also listed as problem 38 in the Ramsey Theory graph-problem collection. There were no page comments or literature updates to incorporate.

Literature audit and exact asymptotic gap

Define

Thus \(T_r(x)\) has \(r-1\) exponentials, matching the live page's convention.

(b) Mubayi and Suk, Off-diagonal hypergraph Ramsey numbers, arXiv:1505.05767, §1.1, record the Erdős–Hajnal–Rado bounds

and, for fixed \(r\geq4\),

They cite the original Erdős–Hajnal–Rado paper, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196. I downloaded and checked that the cited PDF exists and has the stated authors/title (local SHA-256 87cc61e903dd895cddb98299a875ff41bcc3e3183799010d12450b2838412467).

(b) A very recent relevant primary source is Dobák and Mulrenin, Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers, arXiv:2605.16607, posted 2026-05-15. Their Corollary 2 gives

Their Remark 3 says this matches the current best upper bound for \(k=3\) and improves lower-order quantitative terms for \(k\geq4\). It does not remove the missing exponential in the lower bound.

(b) The stepping-up lemma quoted by Mubayi–Suk shows that a lower bound

for some constant \(c>0\) would step up to the requested lower bound for every fixed \(r\geq4\). Conversely, problem 562 itself includes \(r=3\). Therefore the exact uniform missing statement is:

This is the point at which the conjecture remains open; proving only one fixed case, or only a finite list of cases, cannot supply the required uniformity.

(a) The elementary first-moment calculation explains the scale of the known easy lower bound. In a uniformly random coloring, a fixed \(n\)-set is monochromatic with probability

Hence the expected number of monochromatic \(n\)-sets is

Taking \(\log_2 N=(1/6-o(1))n^2\) can make this expectation less than one, because \(\binom n3/n=(n-1)(n-2)/6\). This proves only \(N=2^{\Theta(n^2)}\); it cannot reach \(N=2^{2^{\Theta(n)}}\). This diagnoses the first-moment method only, not every possible probabilistic method.

(b) Mubayi–Suk also give the clean quantitative reduction

where \(P_{k+1}\) is the ordered \(k\)-uniform tight path on \(k+1\) vertices. Their Corollary 1.8 says the corresponding tower conjecture for these path-versus-clique numbers is equivalent to the diagonal conjecture. This is a genuine equivalence, not an available solution.

For finite context, McKay and Radziszowski computationally proved \(R_3(4)=13\) in The First Classical Ramsey Number for Hypergraphs Is Computed. (b) The 2026 revision of Radziszowski's Small Ramsey Numbers, §7.1, still lists this as the only known nontrivial exact classical hypergraph Ramsey number and lists \(88\leq R(5,5;3)\).

I found no primary source claiming the missing diagonal lower bound. This is an honest search result, not a proof of absence. The May 2026 Dobák–Mulrenin preprint is especially useful current evidence because it explicitly identifies the best \(r_3(t,t)\) upper bound while leaving the tower-height gap intact.

A compact explicit \(R_3(5)\geq88\) certificate

Provenance and independent ingestion audit

The author-hosted Dybizbański addendum links a raw 87-vertex coloring. The associated published paper is A lower bound on the hypergraph Ramsey number \(R(4,5;3)\), Contributions to Discrete Mathematics 13(2) (2018), 112–115; the \(R(5,5;3)\) item itself is identified as a 2018 personal communication/addendum in the 2026 Small Ramsey Numbers survey.

(d) I downloaded the raw file independently. It had:

• 2,083,353 bytes and 105,996 lines;
• first line 87;
• exactly \(\binom{87}{3}=105,995\) distinct triple-color lines; and
• SHA-256

cc6b85a5428831663eb75a118ad094bf3bbed6e3866b7becb1fd75c5930a72f9.

(d) Parsing from scratch established all of the following before compression:

• every triple occurred exactly once;
• translation by every \(d\in\mathbb Z/87\mathbb Z\) preserved its color;
• all members of every translation orbit agreed; and
• reconstructing all 105,995 colors from the compressed orbits exactly reproduced the

downloaded file.

Exact construction

Let \(V=\mathbb Z/87\mathbb Z\). For a triple \(e=\{x,y,z\}\), define

Every \(\rho(e)\) has the form \((0,a,b)\). The standalone verifier contains an explicit set \(S\) of 609 pairs \((a,b)\), and defines

The sorted serialization a,b\n of \(S\) has SHA-256 113ef7c08f25115a8cacd73c4f0732ed8ae6fb8fdea076892656859f5f16578f. This digest is asserted by the verifier, so an accidental edit to the certificate is detected.

(d) There are 1,219 triple orbits: 609 red and 610 blue. On labeled triples this is 52,983 red and 53,012 blue. The orbit count is not simply \(\binom{87}{3}/87\), because the orbit of \(\{0,29,58\}\) has a nontrivial stabilizer; the verifier discovers the 1,219 representatives directly.

Why the orbit check is exhaustive

(a) A 5-set in \(\mathbb Z/87\mathbb Z\), read cyclically, is represented by a positive gap composition

up to cyclic rotation. Conversely every such composition gives a 5-set up to translation. There are

rotation classes: no composition is fixed by a nontrivial rotation because 5 is prime and \(5\nmid87\).

(a) No 5-set is fixed by a nonzero translation: each orbit of such a translation has size \(>1\) dividing 87, while an invariant set must be a union of those orbits and \(\gcd(5,87)=1\). Thus every 5-set translation orbit has size 87, and indeed

Checking one canonical gap composition therefore checks every 5-set, without a sampling assumption.

(d) The default verifier checked all 424,711 gap representatives and found both colors on every one. As a separate implementation path, --full used a precomputed labeled-triple table and literally checked all 36,949,857 five-sets. Both passed.

(a), conditional on the finite exhaustive computation (d). Since this coloring on 87 vertices contains no monochromatic \(K^{(3)}_5\), the definition immediately gives

This is a finite lower bound only. It neither improves the presently listed value nor supplies a family with \(n\to\infty\).

A uniform obstruction to the naive tournament lift

The following elementary observation isolates a concrete failure of a standard-looking attempt to turn graph/tournament data into the missing two-color 3-uniform construction.

(a) Proposition. Let \(T\) be any tournament on coordinates \(\{0,\ldots,m-1\}\). For binary strings \(x<y<z\), let

and color \(\{x,y,z\}\) red exactly when the tournament arc points

Then the resulting coloring on all \(2^m\) binary strings contains a red set of size \(m+1\).

(a) Proof. Recursively form a word \(W(S)\) on any coordinate subset \(S\). If \(S=\varnothing\), set \(W(S)\) empty. Otherwise let \(h=\max S\), put

and set

Write \(W(\{0,\ldots,m-1\})=d_1,\ldots,d_m\), and define

These \(m+1\) integers are strictly increasing binary strings.

For \(i<j\),

The recursive tree defining \(W\) is exactly the max-Cartesian tree of the word, since each root \(h\) is the largest coordinate in its recursive block. For any \(v_i<v_j<v_k\), the maxima of the two adjacent word intervals are in an ancestor–descendant relation. If the left maximum is a left descendant of the right maximum, the definition of \(L\) orients it toward its ancestor. If the left maximum is the ancestor of the right maximum, the latter is a right descendant and the definition of \(R\) again orients the arc from the left maximum to the right maximum. Thus every triple from \(\{v_0,\ldots,v_m\}\) is red. \(\square\)

(a) Consequence. To avoid a monochromatic \(n\)-set, this particular lift would need \(m+1<n\), and hence would use at most \(2^{n-2}\) vertices. It cannot produce the desired double exponential. This proposition rules out exactly the tournament-orientation lift above; it does not rule out more elaborate stepping-up rules.

(d) As an independent finite audit of the proof, the verifier enumerates every tournament for \(2\leq m\leq5\) (1,098 tournaments total), constructs the recursive word and lifted vertices, and checks every triple in the asserted red \((m+1)\)-set.

The next cyclic instance: exact formulation and bounded experiment

The cyclic ansatz for 88 vertices has a compact exact SAT quotient.

(a) Since \(\gcd(3,88)=\gcd(5,88)=1\), all triple and 5-set translation orbits are free. Therefore there are exactly

Boolean orbit variables and

5-set orbits. For each 5-set orbit with distinct triple-orbit variables \(x_1,\ldots,x_\ell\), the two clauses

say that its ten triples are not monochromatic.

The core generator used was:

for five_gap_orbit in canonical_positive_compositions(88, 5):
    vertices = partial_sums(five_gap_orbit)
    variables = sorted({
        triple_orbit_id(edge)
        for edge in combinations(vertices, 3)
    })
    solver.add_clause(variables)
    solver.add_clause([-v for v in variables])

(d) A from-scratch quotient audit found the following distribution of the number \(\ell\) of distinct variables in a 5-set constraint:

These sum to 445,179. The optional --audit-n88 path rebuilds these counts independently.

(d) I gave the resulting 890,358-clause formula to PySAT's CaDiCaL 1.9.5 backend. A plain run was interrupted after about 120 solver-seconds; a second run whose phases were seeded by the 87-vertex gap coloring was interrupted after about 90 solver-seconds. Neither returned a model nor an UNSAT certificate. Therefore this experiment gives no lower bound at 89 and no nonexistence result for cyclic colorings at 88.

(c) A realistic next bounded computation would be a solver portfolio of 32 randomized two-hour runs, about 64 core-hours, followed—if UNSAT appears plausible—by a proof-producing solver and independent DRAT/LRAT checking. This is an experimental budget, not a runtime guarantee; a genuine UNSAT proof could cost much more. Even a resolution of this 88-vertex cyclic instance would not address the required asymptotic uniformity.

Reproduction

The standalone artifact is runs/erdos562_wave6c_verify.py. It uses only the Python standard library and embeds the complete 609-orbit certificate.

Its SHA-256 at report time is 40e26a3aba0e7b9afa1d07b624440391ed45b70bf6c8cd14404ed2a449e35551.

Commands:

python runs/erdos562_wave6c_verify.py
python runs/erdos562_wave6c_verify.py --full
python runs/erdos562_wave6c_verify.py --audit-n88

Observed output:

PASS: certificate data; 1,219 triple orbits (609 red/610 blue); 424,711 five-set orbits; 1,098 small tournament lifts; 9.911s
PASS: explicit 87-vertex colouring proves R_3(5) >= 88

PASS: direct check of all 36,949,857 five-sets; 31.911s

PASS: N=88 cyclic quotient has 1,247 variables, 445,179 five-set orbits, clause-length distribution {6: 42, 7: 65, 8: 920, 9: 6680, 10: 437472}; 11.170s

The script also passed python -m py_compile.

PARTIAL: verified a compact explicit 87-vertex coloring proving the known bound \(R_3(5)\geq88\), proved a uniform no-go theorem for the naive tournament stepping-up lift, and isolated the still-missing \(R_3(n)\geq2^{2^{\Omega(n)}}\) lemma; the 88-vertex cyclic SAT instance remains unresolved.