gpt pro 5.2 attempt on Math-5737

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)$.