Reused writeup on Math-5737 (gpt pro 5.2)

Erdős Problem 562 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/562

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/562.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/562.tex.

FORMAL RESTATEMENT

Fix an integer $r\ge 3$ and define $R_r(n)$ to be the least integer $m$ such that for every map $c:\binom{[m]}{r}\to\{\text{red},\text{blue}\}$ there exists $S\subseteq[m]$ with $|S|=n$ such that all $r$-subsets of $S$ receive the same colour. Here $\binom{[m]}{r}$ denotes the set of $r$-element subsets of $[m]=\{1,\dots,m\}$. We take iterated logarithms base $2$: $\log_1 x = \log_2 x$ and $\log_k x = \log_2(\log_{k-1} x)$ for $k\ge 2$. The claim in the problem is that for each fixed $r\ge 3$ there exist constants $c_r,C_r>0$ such that for all $n\ge 2$, \[ c_r n \le \log_{r-1} R_r(n) \le C_r n. \]

QUICK LITERATURE/CONTEXT CHECK

The statement is attributed (in the problem text) to Erdős, Hajnal, and Rado $1965$. The file itself asserts the tower-type upper bound $R_3(n) < 2^{2^{n}}$ and the lower bound $R_3(n) > 2^{c n^2}$ for some $c>0$ (see also Problem 564). No other literature results are assumed here.

ATTACK PLAN

Proof track: $1$ Prove the classical Erdős--Rado stepping-down recursion which bounds $R_r(n)$ in terms of $R_{r-1}(n-1)$. $2$ Combine this recursion with a standard exponential upper bound for graph Ramsey numbers to deduce the tower-type upper bound $\log_{r-1} R_r(n) \ll_r n$.

Disproof/construction track: $1$ Use the probabilistic method (first moment) for a random $2$-colouring of $r$-edges to obtain a general lower bound $R_r(n) > 2^{c_r n^{r-1}}$. $2$ Compare the resulting iterated logarithm with the conjectured linear growth; note it is far smaller for $r\ge 3$.

WORK

Lemma 562.1 (Erdős--Rado stepping-down, explicit). Let $r\ge 3$ and let $t\ge 1$ be an integer. Set \[ N := (t+1) 2^{\binom{t}{r-1}} + 1. \] For every $2$-colouring of the edges of the complete $r$-uniform hypergraph on $N$ vertices there exist distinct vertices $v_1,\dots,v_{t+1}$ such that the following holds: for every $(r-1)$-subset $B\subseteq\{v_1,\dots,v_t\}$, if $j$ is the largest index with $v_j\in B$, then the colour of the $r$-edge $B\cup\{x\}$ is the same for all $x\in\{v_{j+1},\dots,v_{t+1}\}$. In particular, defining a derived $2$-colouring $d$ of $\binom{\{v_1,\dots,v_t\}}{r-1}$ by \[ d(B) := \text{colour of } B\cup\{v_{j+1}\} \quad (j=\max\{i: v_i\in B\}), \] this is well-defined.

Proof. We construct nested sets $S_0\supseteq S_1\supseteq\cdots\supseteq S_t$ and vertices $v_1,\dots,v_{t+1}$ as follows. Start with $S_0=[N]$. For each $j=1,2,\dots,t$ do: choose any $v_j\in S_{j-1}$, and for each $x\in S_{j-1}\setminus\{v_j\}$ define the pattern \[ P_j(x) := \left( c(A\cup\{v_j\}\cup\{x\}) \right)_{A}, \] where $A$ ranges over all $(r-2)$-subsets of $\{v_1,\dots,v_{j-1}\}$. There are exactly $\binom{j-1}{r-2}$ such sets $A$, hence at most $2^{\binom{j-1}{r-2}}$ possible patterns. By the pigeonhole principle, some pattern occurs on at least \[ \frac{|S_{j-1}|-1}{2^{\binom{j-1}{r-2}}} \] choices of $x$. Let $S_j$ be the set of all $x\in S_{j-1}\setminus\{v_j\}$ that realise that most common pattern. Then, for each fixed $(r-2)$-subset $A\subseteq\{v_1,\dots,v_{j-1}\}$, the colour of the $r$-edge $A\cup\{v_j\}\cup\{x\}$ is constant as $x$ varies over $S_j$ (because all $x\in S_j$ have the same pattern). Also we have the size bound \[ |S_j| \ge \frac{|S_{j-1}|-1}{2^{\binom{j-1}{r-2}}}. \]

We claim by induction on $j=0,1,\dots,t$ that \[ |S_j| \ge (t+1-j) 2^{\binom{t}{r-1} - \binom{j}{r-1}}. \tag{$*$} \] For $j=0$ this holds because $|S_0|=(t+1)2^{\binom{t}{r-1}}+1\ge (t+1)2^{\binom{t}{r-1}}$ and $\binom{0}{r-1}=0$. Assume ($*$) holds for $j-1$ with $1\le j\le t$. Using the size bound and ($*$) for $j-1$, \[ |S_j| \ge \frac{(t+2-j)2^{\binom{t}{r-1} - \binom{j-1}{r-1}}-1}{2^{\binom{j-1}{r-2}}}. \] Since $\binom{t}{r-1} - \binom{j-1}{r-1}\ge 0$, we have $2^{\binom{t}{r-1} - \binom{j-1}{r-1}}\ge 1$, hence $(t+2-j)2^{\binom{t}{r-1} - \binom{j-1}{r-1}}-1\ge (t+1-j)2^{\binom{t}{r-1} - \binom{j-1}{r-1}}$. Therefore \[ |S_j| \ge (t+1-j)2^{\binom{t}{r-1} - \binom{j-1}{r-1} - \binom{j-1}{r-2}}. \] Using the Pascal identity $\binom{j}{r-1}=\binom{j-1}{r-1}+\binom{j-1}{r-2}$, this becomes exactly ($*$). In particular, for $j=t$ we get $|S_t|\ge 1$, so we may choose $v_{t+1}\in S_t$.

Now fix any $(r-1)$-subset $B\subseteq\{v_1,\dots,v_t\}$ and let $j$ be the maximum index with $v_j\in B$. Write $B=A\cup\{v_j\}$ where $A$ has size $r-2$ and lies in $\{v_1,\dots,v_{j-1}\}$. By construction at step $j$, the colour of $A\cup\{v_j\}\cup\{x\}$ is constant for all $x\in S_j$. Since the sets are nested, all later vertices $v_{j+1},\dots,v_{t+1}$ lie in $S_j$, so the colour of $B\cup\{v_k\}$ is the same for every $k>j$. This proves the stated extension property. Finally, the definition of $d(B)$ using $v_{j+1}$ is therefore independent of the choice of later vertex, so $d$ is well-defined. $\square$

Corollary 562.2 (recursion for Ramsey numbers). Let $r\ge 3$ and $n\ge 2$, and set $t:=R_{r-1}(n-1)$. Then \[ R_r(n) \le (t+1) 2^{\binom{t}{r-1}} + 1. \]

Proof. Apply Lemma 562.1 with this $t$. The derived colouring $d$ is a $2$-colouring of the complete $(r-1)$-uniform hypergraph on $\{v_1,\dots,v_t\}$. Since $t=R_{r-1}(n-1)$, there exists a set $U\subseteq\{v_1,\dots,v_t\}$ of size $n-1$ such that every $(r-1)$-subset of $U$ has the same $d$-colour, say red. We claim that $U\cup\{v_{t+1}\}$ is a red copy of $K_n^{(r)}$ in the original $r$-uniform hypergraph. Take any $r$-subset $E\subseteq U\cup\{v_{t+1}\}$. Let $w$ be the vertex of $E$ with largest index (so $w=v_j$ for some $j\le t+1$) and set $B=E\setminus\{w\}$, which has size $r-1$. Then the maximum index in $B$ is some $j' < j$, and by the extension property from Lemma 562.1, all $r$-edges of the form $B\cup\{x\}$ with $x\in\{v_{j'+1},\dots,v_{t+1}\}$ have the same colour, namely $d(B)$. Since $w$ is one of these later vertices, the colour of $E=B\cup\{w\}$ equals $d(B)$. But $B\subseteq U$, so $d(B)$ is red. Hence every $r$-edge $E$ is red, proving the claim. Thus any $2$-colouring on $N=(t+1)2^{\binom{t}{r-1}}+1$ vertices forces a monochromatic $K_n^{(r)}$, so $R_r(n)\le N$. $\square$

Lemma 562.3 (tower-type upper bound, proved from the recursion). For each fixed $r\ge 2$ there exists a constant $C_r>0$ such that for all $n\ge 2$, \[ \log_{r-1} R_r(n) \le C_r n. \]

Proof. We proceed by induction on $r$. For $r=2$, the standard recursion for graph Ramsey numbers gives $R_2(n)\le 4^n$ (see the quick proof below), hence $\log_1 R_2(n)=\log_2 R_2(n)\le 2n$, so the claim holds with $C_2=2$.

Assume $r\ge 3$ and the claim is true for $r-1$. Let $t=R_{r-1}(n-1)$ and apply Corollary 562.2: \[ R_r(n) \le (t+1)2^{\binom{t}{r-1}} + 1. \] For $t\ge 2$ (which holds for all $n\ge 3$), we have $t+1\le 2^t$, hence \[ R_r(n) \le 2^t 2^{\binom{t}{r-1}} 2 = 2^{\binom{t}{r-1}+t+1}. \] Taking base-$2$ logarithms gives \[ \log_2 R_r(n) \le \binom{t}{r-1}+t+1 \le t^{r-1} + t + 1. \] Now apply $\log_{r-2}$ to both sides (note $r-2\ge 1$): \[ \log_{r-1} R_r(n) = \log_{r-2}(\log_2 R_r(n)) \le \log_{r-2}(t^{r-1}+t+1). \] For $t\ge 2$, we have $t^{r-1}+t+1\le 2t^{r-1}$, hence \[ \log_{r-2}(t^{r-1}+t+1) \le \log_{r-2}(2t^{r-1}). \] If $r-2=1$ this is $\log_2(2t^{r-1}) = 1+(r-1)\log_2 t$. If $r-2\ge 2$, then iterated logarithms satisfy $\log_{r-2}(2t^{r-1}) = \log_{r-2}(t^{r-1}) + O_r(1)$ and $\log_{r-2}(t^{r-1}) = \log_{r-2}(t)+O_r(1)$. In all cases, we obtain \[ \log_{r-1} R_r(n) \le \log_{r-2}(t) + O_r(1) = \log_{r-2}(R_{r-1}(n-1)) + O_r(1). \] By the induction hypothesis for $r-1$, $\log_{r-2}(R_{r-1}(n-1))\le C_{r-1}(n-1)$. Thus $\log_{r-1} R_r(n) \le C_{r-1}(n-1)+O_r(1)$, which is at most $C_r n$ for a suitable constant $C_r$ and all $n\ge 2$. $\square$

(Quick proof used above: $R_2(n)\le 4^n$.) Set $R(s,t)$ to be the usual graph Ramsey number for red $K_s$ vs blue $K_t$. The classical recursion $R(s,t)\le R(s-1,t)+R(s,t-1)$ follows by picking a vertex $v$ and splitting its neighbours by colour. With $R(1,t)=R(s,1)=1$, induction yields $R(s,t)\le \binom{s+t-2}{s-1}\le 2^{s+t-2}$. In particular $R_2(n)=R(n,n)\le 2^{2n-2}\le 4^n$.

Lemma 562.4 (probabilistic lower bound). For each fixed $r\ge 2$ there exists a constant $c_r>0$ such that for all $n\ge r$, \[ R_r(n) > 2^{c_r n^{r-1}}. \]

Proof. Fix $m$ and $2$-colour each $r$-edge of $K_m^{(r)}$ independently red/blue with probability $1/2$. For a fixed $n$-vertex subset $S$, the probability that all $\binom{n}{r}$ edges of $S$ are monochromatic is \[ 2\cdot 2^{-\binom{n}{r}} = 2^{1-\binom{n}{r}}. \] Let $X$ be the number of monochromatic copies of $K_n^{(r)}$. By linearity of expectation, \[ \mathbb{E}X = \binom{m}{n} 2^{1-\binom{n}{r}}. \] Using $\binom{m}{n}\le (em/n)^n$, it suffices to ensure \[ (em/n)^n < 2^{\binom{n}{r}-1}. \] Assume $n\ge 2r$. Then $\binom{n}{r} = \frac{n(n-1)\cdots(n-r+1)}{r!} \ge \frac{(n/2)^r}{r!}$. Choose $m = \lfloor 2^{c n^{r-1}}\rfloor$ where $c>0$ will be specified. Then \[ \log_2((em/n)^n) = n\left(\log_2 m + \log_2(e/n)\right) \le n\left(c n^{r-1} + 2\log_2 n\right) \] for all $n\ge 2$. On the other hand, \[ \binom{n}{r}-1 \ge \frac{(n/2)^r}{r!}-1. \] For large enough $n$, the term $2n\log_2 n$ is negligible compared to $n^r$, so it is enough to take (for instance) \[ c_r := \frac{1}{2^{r+2} r!} \] so that for all sufficiently large $n$ we have $n\cdot c_r n^{r-1} \le \frac{1}{4}\cdot \frac{(n/2)^r}{r!} \le \frac{1}{2}(\binom{n}{r}-1)$. Then $\mathbb{E}X<1$, so there exists a colouring with $X=0$, i.e. with no monochromatic $K_n^{(r)}$ on $m$ vertices. Thus $R_r(n)>m\ge 2^{c_r n^{r-1}-1}$; adjusting $c_r$ gives the stated form. $\square$

VERIFICATION

$1$ Quantifiers/conventions: $R_r(n)$ is defined for integers $r\ge 2$ and $n\ge r$. All logarithms above are base $2$; changing base changes the constants but not the $\asymp_r$ statement.

$2$ Boundary cases: For $n=r$, the statement is trivial because $R_r(r)=r$. All inequalities above were proved for $n\ge 3$ or $n\ge 2r$ where stated; finitely many small $n$ can be absorbed into constants.

$3$ Fast reality check by computation (first-moment lower bound threshold). For a random $2$-colouring of $r$-edges on $m$ vertices, $\mathbb{E}X = \binom{m}{n}2^{1-\binom{n}{r}}$. A brute computation of the largest $m$ with $\mathbb{E}X<1$ gives: for $r=3$: $n=4$ gives $m=5$, $n=5$ gives $m=11$, $n=6$ gives $m=29$, $n=7$ gives $m=100$, $n=8$ gives $m=445$; for $r=4$: $n=5$ gives $m=6$, $n=6$ gives $m=17$, $n=7$ gives $m=100$, $n=8$ gives $m=1489$. (These are only sanity checks; the first-moment method is far from tight for small $n$.)

FINAL

UNRESOLVED

(i) Strongest proved partial result here: for each fixed $r\ge 3$, \[ \log_{r-1} R_r(n) \le C_r n \qquad\text{and}\qquad R_r(n) > 2^{c_r n^{r-1}}. \] The upper bound matches the conjectured order, but the lower bound is vastly weaker when expressed as an $(r-1)$-fold iterated logarithm.

(ii) First gap (crisp): prove a tower-type lower bound \[ \log_{r-1} R_r(n) \ge c_r n\quad\text{for some }c_r>0 \text{ and all large }n. \] Equivalently, construct (or prove the existence of) $2$-colourings of $K_m^{(r)}$ for $m$ of height-$(r-1)$ tower size in $n$ with no monochromatic $K_n^{(r)}$.

(iii) Top 3 next moves: $1$ For $r=3$, seek an explicit stepping-up construction improving the probabilistic $2^{c n^2}$ lower bound to $2^{2^{c n}}$. $2$ Try to isolate a structured family of colourings (e.g. algebraic colourings over $\mathbb{F}_2^d$) and prove they avoid monochromatic $K_n^{(r)}$ up to tower size. $3$ Computationally: for small $n$ and $r=3,4$, search for colourings beating the first-moment bound, to guess viable constructions (e.g. via SAT search on $K_m^{(r)}$).

(iv) Minimal counterexample structure: a counterexample to the conjectured lower bound would be a fixed $r\ge 3$ and infinitely many $n$ for which $R_r(n)$ is bounded above by a height-$(r-1)$ tower whose top exponent is $o(n)$. Equivalently, it would give $2$-colourings on $m$ vertices with $m$ a height-$(r-1)$ tower in $n$ but with no monochromatic $K_n^{(r)}$, forcing $\log_{r-1} R_r(n)=o(n)$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.