codex 5.2 extra high attempt on Math-5739

FORMAL RESTATEMENT

Let $R_3(n)$ be the least $m$ such that every red/blue colouring of the edges of the complete $3$-uniform hypergraph on $m$ vertices contains a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices. The question asks whether there exists an absolute constant $c>0$ such that \[ R_3(n) \ge 2^{2^{c n}} \qquad\text{for all sufficiently large }n. \]

QUICK LITERATURE/CONTEXT CHECK

The file states that Erdős--Hajnal--Rado $1965$ proved bounds $2^{c n^2} < R_3(n) < 2^{2^{n}}$ for some constant $c>0$. I will not use any additional results beyond what is proved here.

ATTACK PLAN

Proof track: Use the stepping-down lemma from Problem 562 to re-derive a double-exponential upper bound $R_3(n)\le 2^{2^{O(n)}}$.

Disproof/construction track: Use the probabilistic method to obtain the classical lower bound $R_3(n) > 2^{c n^2}$. Compare this with the conjectured $2^{2^{c n}}$ lower bound; note the gap is exactly the open difficulty.

WORK

Lemma 564.1 (double-exponential upper bound, proved from stepping-down). There exists an absolute constant $C>0$ such that for all $n\ge 3$, \[ R_3(n) \le 2^{2^{C n}}. \]

Proof. Apply Corollary 562.2 with $r=3$. Then with $t=R_2(n-1)$, \[ R_3(n) \le (t+1) 2^{\binom{t}{2}} + 1 \le 2^{t} 2^{t^2/2} 2 = 2^{t^2/2+t+1}. \] Using the elementary graph Ramsey upper bound $R_2(n-1)\le 4^{n-1}=2^{2n-2}$, we have $t\le 2^{2n}$ for $n\ge 2$. Therefore $t^2/2+t+1 \le 2^{4n}$ for all $n$ large enough, hence \[ R_3(n) \le 2^{2^{4n}}. \] This is of the claimed form with $C=4$. $\square$

Lemma 564.2 (probabilistic lower bound). There exists an absolute constant $c>0$ such that for all $n\ge 3$, \[ R_3(n) > 2^{c n^2}. \]

Proof. This is the case $r=3$ of Lemma 562.4. For completeness, set $m=\lfloor 2^{c n^2}\rfloor$. For a random $2$-colouring of triples on $m$ vertices, the expected number of monochromatic $n$-sets is $\binom{m}{n}2^{1-\binom{n}{3}}$. Using $\binom{m}{n}\le (em/n)^n$ and $\binom{n}{3}\ge n^3/48$ for $n\ge 6$, one checks that for sufficiently small fixed $c>0$ this expectation is $<1$ for all large $n$. Hence some colouring has no monochromatic $K_n^{(3)}$, so $R_3(n)>m$. $\square$

VERIFICATION

$1$ The proof of Lemma 564.1 only uses inequalities valid for $n\ge 3$; finitely many small $n$ are irrelevant to the asymptotic.

$2$ Fast reality check by computation (first-moment threshold for $r=3$): Largest $m$ such that $\binom{m}{n}2^{1-\binom{n}{3}}<1$ is $m=5$ for $n=4$, $m=11$ for $n=5$, $m=29$ for $n=6$, $m=100$ for $n=7$, $m=445$ for $n=8$. These are consistent with the proved lower bound form $2^{c n^2}$ but far below the conjectured $2^{2^{c n}}$.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: there exist absolute constants $c,C>0$ such that \[ 2^{c n^2} < R_3(n) \le 2^{2^{C n}}. \] (The upper bound is re-derived via the stepping-down lemma; the lower bound via the probabilistic method.)

(ii) First gap (crisp): prove or disprove the existence of $c>0$ with \[ R_3(n) \ge 2^{2^{c n}} \quad\text{for all large }n. \]

(iii) Top 3 next moves: $1$ Attempt explicit algebraic or geometric $2$-colourings of triples with $m=2^{2^{c n}}$ and prove they avoid monochromatic $K_n^{(3)}$. $2$ Strengthen the random-colouring argument using dependencies/containers to push beyond $2^{c n^2}$. $3$ Computationally: for small $n$ (say $n=5,6,7$), search for best known lower bounds by SAT/ILP to identify patterns of extremal colourings.

(iv) Minimal counterexample structure: if the conjectured bound fails, then for every $c>0$ there are arbitrarily large $n$ with a $2$-colouring of triples on $m=2^{2^{c n}}$ vertices having no monochromatic $K_n^{(3)}$. Such a construction would have to exhibit long-range structure well beyond what random colourings provide (since random colourings already fail around $m=2^{O(n^2)}$).