Erdoes #564 - working report - Erdős Problem a Day

Erdős problem #564 — wave 6d

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

Outcome

I did not solve the asymptotic problem. I obtained two independently

verifiable outputs:

1. (a) elementary-rigorous: a uniform no-go theorem for every fixed

pointwise two-colour merger of the standard four-colour stepping-up

construction. Every such merger on $N=2^m$ vertices satisfies

$\log_2\log_2 N=o(n)$ if it avoids a monochromatic $n$-set, so this

entire natural class cannot prove the requested

$N\geq 2^{2^{cn}}$.

2. (d) computational-only, with the implication (a): a compact explicit

cyclic colouring of the triples of 87 vertices, checked both modulo

translation and directly on all $36,949,857$ five-sets. This proves the

known finite bound $R_3(5)\geq88$. The certificate is independently

compared with the author-hosted raw colouring.

I also checked an explicit 12-vertex colouring with no monochromatic

four-set. Together with the named McKay--Radziszowski theorem this gives the

small exact value $R_3(4)=13$. (b)/(d)

Claim labels throughout are:

(a) elementary-rigorous;
(b) rigorous modulo an explicitly named theorem or primary source;
(c) plausible/structural-unverified;
(d) computational-only.

Step 0: authoritative live-page gate

I fetched the JavaScript-rendered

live page and its

raw LaTeX view through the Bright

Data browser path. Direct datacenter curl was not used as the authority.

(d)

The live page displayed:

| Field | Live value |

|---|---|

| Status | OPEN - $500 |

| Comments | 0 |

| Claimed proofs | 0 |

| Interested in collaborating | None |

| Currently working on this problem | None |

| Likes this problem | Dogmachine |

| Looks difficult | None |

| Looks tractable | None |

| Results could be formalisable | None |

| Working on formalising | None |

| Formalised statement? | Yes |

| Related OEIS sequences | Possible |

| Last edited | 18 January 2026 |

Thus neither mandatory stop condition fired. (d)

Verbatim current statement

The following is copied verbatim from the live raw-LaTeX endpoint:

> Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices.

> Is there some constant $c>0$ such that\[R_3(n) \geq 2^{2^{cn}}?\]

The page attaches the source markers [EHR65][Er81][Er97c].

Everything else mathematical listed on the page

Again verbatim from the live raw-LaTeX endpoint:

> A special case of [562]. A problem of Erd\H{o}s, Hajnal, and Rado \cite{EHR65}, who prove the bounds\[2^{cn^2}< R_3(n)< 2^{2^{n}}\]for some constant $c>0$.

> Erd\H{o}s, Hajnal, M\'{a}t\'{e}, and Rado \cite{EHMR84} have proved a doubly exponential lower bound for the corresponding problem with $4$ colours.

> This problem is #37 in Ramsey Theory in the graphs problem collection.

The endpoint gives these two references:

[EHR65] P. Erdős, A. Hajnal, and R. Rado, *Partition relations for

cardinal numbers*, Acta Math. Acad. Sci. Hungar. 16 (1965), 93--196.

[EHMR84] P. Erdős, A. Hajnal, A. Máté, and R. Rado,

Combinatorial Set Theory: Partition Relations for Cardinals (1984),

347 pages.

There were no comments, claimed proofs, or worker/interested markers to

incorporate. (d)

Literature audit

The following sources were individually opened; an identifier is not

reported unless the source existed and contained the stated material.

1. (b) The author archive copy of Erdős--Hajnal--Rado,

Partition relations for cardinal numbers,

is a 104-page scan with the stated authors, journal, volume, year, and

pages. Its downloaded SHA-256 was

87cc61e903dd895cddb98299a875ff41bcc3e3183799010d12450b2838412467.

2. (b) Conlon, Fox, and Sudakov,

Hypergraph Ramsey numbers,

arXiv:0808.3760, JAMS 23 (2010), 247--266, explicitly records the

diagonal gap

\[ 2^{\Omega(n^2)}

and the Erdős--Hajnal conjectured doubly exponential lower bound.

Its Section 4 writes the $\delta$-based four-colour stepping-up rule

and then merges one pair of colours to obtain the three-colour bound

\[ r_3(n,n,n)>2^{\,r(\log_2 n,n-1)-1}. \]

This precise rule is the starting point of the merger obstruction below,

not an inferred description.

3. (b) Dobák and Mulrenin,

[*Recursive upper bounds for the vertex online Ramsey game with

applications to hypergraph Ramsey numbers*](https://arxiv.org/abs/2605.16607),

arXiv:2605.16607, submitted 15 May 2026, gives new upper recurrences.

Its Remark 3 says its $r_3(t,t)$ consequence matches the current best

upper bound. It supplies no missing diagonal lower bound.

4. (b) I also checked the very recent Du--Hu--Liu--Wang preprint

A double-exponential lower bound for $r_4(5,n)$,

arXiv:2604.23986, submitted 27 April 2026. It settles the remaining

classical off-diagonal tower-height case; it is not a result about

$r_3(n,n)$.

5. (b) McKay and Radziszowski,

[*The First Classical Ramsey Number for Hypergraphs Is

Computed*](https://www.cs.rit.edu/~spr/PUBL/paper25.pdf),

SODA 1991, 304--308, proves $R(4,4;3)=13$ by computer. The paper

reports about $6\cdot10^{13}$ machine instructions and multiple

independent enumeration paths.

6. (b)/(d) Dybizbański's author-hosted

addendum and data page states

$R(5,5;3)\geq88$ and links the raw

87-vertex colouring.

The associated paper is

[*A lower bound on the hypergraph Ramsey number

$R(4,5;3)$*](https://cdm.ucalgary.ca/article/view/62416),

Contributions to Discrete Mathematics 13(2) (2018), 112--115,

DOI 10.55016/ojs/cdm.v13i2.62416; the $R(5,5;3)$ construction is

specifically the author addendum/personal communication, not a theorem

printed in that article.

7. (b) As a current secondary cross-check, revision 18 (April 2026) of

Radziszowski's

Small Ramsey Numbers,

§7.1, still lists $R(4,4;3)=13$ as the only nontrivial exact classical

hypergraph Ramsey number and lists $88\leq R(5,5;3)$, attributing the

latter to Dybizbański's addendum.

I found no primary source claiming the missing

$r_3(n,n)\geq2^{2^{\Omega(n)}}$ bound. This is an honest search result,

not a proof that no such source exists; the live-page gate remains the

authoritative status check. (d)

Why the independent random colouring stops one exponential early

Give every triple of an $N$-set an independent fair colour. A fixed

$n$-set is monochromatic with probability

\[ 2\cdot2^{-\binom n3}=2^{1-\binom n3}. \]

Hence the expected number of monochromatic $n$-sets is

\[ \binom Nn\,2^{1-\binom n3}. \tag{1} \]

Taking $\log_2N=(1/6-o(1))n^2$ makes (1) less than one and yields

the classical $2^{\Omega(n^2)}$ scale. At

$N=2^{2^{cn}}$, however, the positive contribution

$\log_2\binom Nn\sim n2^{cn}$ overwhelms

$\binom n3=\Theta(n^3)$. Thus the direct first-moment construction

cannot reach the requested scale. This diagnoses that method only, not

all probabilistic methods. (a)

A uniform barrier for every pointwise merge of the four colours

This section gives the main structural output.

Let $\phi:\binom{[m]}2\to\{0,1\}$ be an arbitrary base graph

colouring. Order the $2^m$ binary strings by their integer values and,

for $x\ne y$, put

\[ \delta(x,y)=\max\{i:x_i\ne y_i\}. \]

For \(x

$d_2=\delta(y,z)$; always $d_1\ne d_2$.

The usual four stepping-up colours are the pair

\[ \left(\phi(\{d_1,d_2\}),\ \operatorname{sgn}(d_1-d_2)\right). \]

Fix any Boolean merger

\[ M:\{0,1\}\times\{<,>\}\longrightarrow\{0,1\} \]

and colour the triple by

\[ \chi_M(x,y,z) =M\!\left(\phi(\{d_1,d_2\}), \operatorname{sgn}(d_1-d_2)\right). \tag{2} \]

There are exactly $2^4=16$ such mergers.

Two elementary witness lemmas

Cube lemma (a). Suppose $S\subseteq[m]$ is a clique of base

colour $c$, and $M(c,<)=M(c,>)=q$. Then the $2^{|S|}$ strings

supported on $S$ form a $q$-monochromatic set under (2).

Indeed, both deltas of any triple of those strings lie in $S$; their

base edge has colour $c$, and the sign is irrelevant.

Tournament-word lemma (a). Let $g(i,j)\in\{0,1\}$ be defined for

ordered distinct coordinates and satisfy $g(i,j)=1-g(j,i)$. The lift

$\chi(x,y,z)=g(\delta(x,y),\delta(y,z))$ on all $2^m$ strings

contains a 1-monochromatic set of size $m+1$.

Define a tournament by $i\to j$ iff $g(i,j)=1$. Recursively form a

word $W(S)$: if $S=\varnothing$, it is empty; otherwise, with

$h=\max S$, put

\[ L=\{u\in S\setminus\{h\}:u\to h\},\qquad R=\{u\in S\setminus\{h\}:h\to u\}, \]

and set $W(S)=W(L),h,W(R)$. Write the resulting word as

$d_1,\ldots,d_m$ and take prefix sums

\[ v_0=0,\qquad v_j=\sum_{i=1}^j2^{d_i}. \]

For \(i

intervals $d_{i+1},\ldots,d_j$ and

$d_{j+1},\ldots,d_k$. In the max-Cartesian tree of $W$, those two

maxima are ancestor and descendant. The definitions of $L$ and $R$

orient the first maximum toward the second in either case. Thus every

triple among $v_0,\ldots,v_m$ has colour 1.

Complete classification of the 16 mergers

Call the row $M(c,\cdot)$ dependent if its two values differ and

independent if they agree. Put

\[ a=\lceil\log_2n\rceil,\qquad b=n-1. \]

Theorem (a). If (2) has no monochromatic $n$-set, then:

1. If both rows are dependent, $m\leq n-2$.

2. If both rows are independent and have the same output, then

\(2^m

\[ m

3. If exactly one row is independent, then

\[ m

up to swapping the two base colours.

For (1), the ordered-pair output in (2) orients every coordinate pair,

so the tournament-word lemma gives $m+1$ monochromatic vertices.

For (2), the equal-output case makes the entire lift constant. In the

different-output case, a base clique of either colour on $a$

coordinates gives $2^a\geq n$ monochromatic strings by the cube

lemma. For (3), a base clique of size $a$ in the independent row

again gives a cube of size at least $n$, while a base clique of size

$b$ in the dependent row gives $b+1=n$ vertices by the

tournament-word lemma. The standard recursion

$r(s,t)\leq r(s-1,t)+r(s,t-1)$ gives the displayed binomial bounds.

Consequently,

\[ \log_2m= \begin{cases} O(\log n),&\text{both rows of the same type},\\ O((\log n)^2),&\text{one row of each type}, \end{cases} \]

using $\binom uv\leq(eu/v)^v$ in the mixed case. Since the lifted

number of vertices is $N=2^m$,

\[ \boxed{\log_2\log_2N=\log_2m=o(n).} \tag{3} \]

The conjectured construction would require

$\log_2\log_2N\geq cn$. Therefore **no fixed pointwise merger of the

standard four colours into two can prove problem 564**, regardless of

the choice of the base graph $\phi$. (a)

This does not rule out a rule using more of the delta sequence, a

nonlocal merger, or a completely different construction. In particular,

it does not prove an upper bound on $R_3(n)$. (a)

Independent finite audit (d). The checker exhausts every base graph

on $2\leq m\leq5$ coordinates and all 16 mergers. For each of the

17,568 cases it constructs and directly checks the cube or

tournament-word witness used above.

An explicit 87-vertex certificate

Provenance and ingestion audit

I downloaded the author-hosted r55_87.txt independently. It had:

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

cc6b85a5428831663eb75a118ad094bf3bbed6e3866b7becb1fd75c5930a72f9.

Every line was parsed from scratch, every triple occurred exactly once,

and every listed colour was compared with the compact certificate below.

(d)

Exact compact construction

Let $V=\mathbb Z/87\mathbb Z$. For a triple $e$, define

\[ \rho(e)=\min_{d\in e}^{\rm lex} \operatorname{sort}\bigl((e-d)\bmod87\bigr). \]

Sort lexicographically the set of all representatives

$\rho(e)$, obtaining

\[ q_0,q_1,\ldots,q_{1218}. \]

Let $C$ be the following hexadecimal integer:

246d70e3648e1d32c26182a5c5f19ef060e28aa4cb2fee1a0071f1257d24e73b5c3e2ea4c633617c78e2d35b2a349aa8f41b24b223157a897e6715e089713ef6e2be44981ecfb971f4f7de42133f5612f8936fdae01b33a9577a2bb4c2e488f8ab72ed5d0812c68ccb8b656475a5ac0abe0cb353e662c6a2371af146caa29b56bd48e6963a6a65227e661cb7d306adbd1c27e64422c65dc5e

Colour $e$ red exactly when bit $i$ of $C$, counted from the

least significant bit as bit 0, is 1 for $\rho(e)=q_i$; otherwise

colour it blue. This is a fully explicit 1219-bit certificate. Its

hexadecimal string has SHA-256

6b14c87d9110393db5821922fa0bc96371377fe161a568712b9453bf14ef8422.

There are 609 red representatives and 610 blue representatives.

On labelled triples there are 52,983 red and 53,012 blue triples.

The exceptional triple orbit represented by $\{0,29,58\}$ has

size 29, explaining why the orbit count is 1,219 rather than a

nonintegral $\binom{87}{3}/87$. (d)

Exhaustiveness of the five-set check

A five-set on the cyclic group gives a positive gap composition

\[ (g_1,\ldots,g_5),\qquad g_1+\cdots+g_5=87, \]

up to cyclic rotation. Conversely, every such composition gives a

five-set up to translation. No composition has a nontrivial rotational

stabiliser: 5 is prime, and a period-one composition would require

$5\mid87$. Thus the number of gap orbits is

\[ \frac{1}{5}\binom{86}{4}=424,711. \tag{4} \]

No five-set is fixed by a nonzero translation, since every nontrivial

translation cycle has length $>1$ dividing 87, whereas

$\gcd(5,87)=1$. Therefore every translation orbit has size 87, and

\[ 424,711\cdot87=\binom{87}{5}=36,949,857. \tag{5} \]

Equations (4)--(5) prove that one canonical gap representative covers

every labelled five-set. (a)

The checker found both colours on every one of the 424,711

representatives. A separate implementation then directly inspected all

$36,949,857$ labelled five-sets and obtained the same result. (d)

It follows immediately from the definition that

\[ \boxed{R_3(5)>87,\quad\text{hence}\quad R_3(5)\geq88.} \]

(a), conditional on the exhaustive finite computation (d).

This is a known finite bound, not a claimed improvement and not an

asymptotic construction.

Verified small-case table

| $n$ | Verified statement | Status |

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

| 3 | $R_3(3)=3$ | (a) immediate |

| 4 | $R_3(4)=13$ | (b) McKay--Radziszowski; embedded 12-vertex lower certificate checked (d) |

| 5 | $R_3(5)\geq88$ | explicit certificate and exhaustive check (d) |

The 12-vertex certificate is a 220-bit colour vector in lexicographic

triple order, embedded in the checker as

b9cc792b96c19ad1f8b0b0b265f8670ca2ec7d1e8358a95314d9af2.

It has 110 triples of each colour, and every one of the

$\binom{12}{4}=495$ four-sets contains both colours. (d)

Exact remaining wall and bounded-computation cost

The uniform missing lemma is exactly:

\[ \boxed{\text{For some }c>0\text{ and every sufficiently large }n, \text{ construct a two-colouring of } \binom{[\,2^{2^{cn}}\,]}3 \text{ with no monochromatic }n\text{-set}.} \]

The pointwise-merger theorem proves that the colouring rule must use

strictly more information than the base pair colour and the comparison

of the two adjacent deltas (or use a different framework). (a)

For finite context, the unsymmetrised SAT formula for $R_3(4)\leq13$

has 286 variables and 1,430 length-four clauses. A plain CaDiCaL 1.9.5

run was interrupted after about 120 seconds without a result; this is

not used as evidence for SAT or UNSAT. The 1991 named theorem supplies

the upper bound. (d)

The next cyclic $R_3(5)$ instance, on 88 vertices, has exactly

\[ \binom{88}{3}/88=1,247 \]

translation-orbit variables and

\[ 2\binom{88}{5}/88=890,358 \]

non-monochromaticity clauses, because the translation actions on

triples and five-sets are free. (a) A reasonable experiment would

be a 32-seed solver portfolio for two hours per seed, i.e. 64 core-hours,

followed by proof-producing and independently checked DRAT/LRAT work if

UNSAT appears plausible. This is a budget estimate, not a runtime

guarantee; proof generation could cost much more. (c)

Even a complete decision of that cyclic 88-vertex instance would be

only a finite structured result. No finite list of cases supplies the

uniformity in the boxed missing lemma. (a)

Reproduction

Standalone checker:

runs/erdos564_wave6d_reverify.py

Report-time SHA-256:

ef9e965656e42be8926340564386e56803f0462128881116e5a2f30eeea54b73.

Commands run:

python -m py_compile runs/erdos564_wave6d_reverify.py
python runs/erdos564_wave6d_reverify.py
python runs/erdos564_wave6d_reverify.py \
  --full --source /tmp/r55_87.txt

Observed output:

PASS: 12-vertex K4-free-in-both-colours certificate; 424,711 cyclic 5-set orbits on 87 vertices; 17,568 exhaustive small merger cases; 19.338s
PASS: explicit cyclic colouring proves R_3(5) >= 88

PASS: 12-vertex K4-free-in-both-colours certificate; 424,711 cyclic 5-set orbits on 87 vertices; 17,568 exhaustive small merger cases; 19.331s
PASS: explicit cyclic colouring proves R_3(5) >= 88
PASS: direct check of all 36,949,857 labelled 5-sets; 31.878s
PASS: author source checksum, syntax, completeness, and all colours match; 0.684s

PARTIAL: proved a uniform barrier excluding every fixed pointwise two-colour merge of the standard four-colour stepping-up construction, and independently verified the known explicit 87-vertex colouring $R_3(5)\geq88$; the required uniform double-exponential two-colour construction remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger