gpt pro 5.2 attempt on Math-6083

If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, then\[\frac{R(k)}{k2^{k/2}}\to \infty.\] In [Er93] Erdős offers \$100 for a proof of this and \$1000 for a disproof, but says 'this last offer is to some extent phoney: I am sure that [this] is true (but I have been wrong before).' Erdős and Szekeres [ErSz35] proved\[k2^{k/2} \ll R(k) \leq \binom{2k-1}{k-1}.\]One of the first applications of the probabilistic method pioneered by Erdős gives\[R(k) \geq (1+o(1))\frac{1}{\sqrt{2}e}k2^{k/2},\]which Spencer [Sp75] improved by a factor of $2$ to\[R(k) \geq (1+o(1))\frac{\sqrt{2}}{e}k2^{k/2}.\]See also [77] for a more general problem concerning $\lim R(k)^{1/k}$, and discussion of upper bounds for $R(k)$. References [Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory . Quaestiones Math. $1993$, 333-350. [ErSz35] Erdős, P. and Szekeres, G., A combinatorial problem in geometry . Compos. Math. $1935$, 463-470. [Sp75] Spencer, Joel, Ramsey's theorem---a new lower bound . J. Combinatorial Theory Ser. A $1975$, 108--115.

Erdős Problem #1029 --- Solution Attempt

FORMAL RESTATEMENT. For each integer $k\ge 2$, let $R(k)$ denote the diagonal Ramsey number $R(k,k)$: the least integer $n$ such that every 2-colouring of the edges of the complete graph $K_n$ contains a monochromatic copy of $K_k$. The conjecture is \[ \lim_{k\to\infty} \frac{R(k)}{k2^{k/2}} = +\infty. \] Equivalently: for every constant $C>0$ there exists $k_0$ such that for all $k\ge k_0$ one has $R(k)\ge C\,k2^{k/2}$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records:

• the Erdős--Szekeres upper bound $R(k)\le \binom{2k-1}{k-1}$,
• a probabilistic-method lower bound with constant $\frac{1}{\sqrt{2}e}$ up to $(1+o(1))$,
• Spencer's improvement by a factor $2$.

I do not use any external results beyond what is explicitly in the problem file.

ATTACK PLAN. Proof track: try to amplify the known probabilistic lower bounds by a factor that tends to infinity (e.g. by iterated random constructions or by showing "random colouring works" at larger $n$ than the first-moment threshold).

Disproof track: try to show $R(k)\le Ck2^{k/2}$ for some constant $C$ (or even along an infinite subsequence), which would require a new type of upper bound.

Given current tools available in this session, I focus on producing rigorous baseline bounds and sanity checks, and then state the precise gap.

WORK.

Lemma 1 (Erdős--Szekeres recursion bound). For integers $s,t\ge 2$, \[ R(s,t) \le \binom{s+t-2}{s-1}. \] In particular, \[ R(k)=R(k,k) \le \binom{2k-2}{k-1} < \binom{2k-1}{k-1}. \]

Proof. We first prove the standard recursion \[ R(s,t) \le R(s-1,t) + R(s,t-1). \tag{R} \] Consider any 2-colouring (red/blue) of the edges of $K_N$ with $N := R(s-1,t)+R(s,t-1)$. Fix a vertex $v$. Let $R_v$ be the set of red neighbours of $v$ and $B_v$ the set of blue neighbours; then $|R_v|+|B_v|=N-1$. If $|R_v|\ge R(s-1,t)$, then by definition of $R(s-1,t)$ the induced complete graph on $R_v$ contains either (i) a red $K_{s-1}$ or (ii) a blue $K_t$. In case (i), adding the vertex $v$ gives a red $K_s$ (since $v$ is joined by red edges to all vertices of that $K_{s-1}$). In case (ii) we already have a blue $K_t$. Similarly, if $|B_v|\ge R(s,t-1)$, then the induced graph on $B_v$ contains either a red $K_s$ or a blue $K_{t-1}$; in the latter case adding $v$ yields a blue $K_t$. Therefore every colouring of $K_N$ contains a red $K_s$ or a blue $K_t$, proving (R).

Now define $f(s,t):=\binom{s+t-2}{s-1}$. It satisfies the same recursion \[ f(s,t)=f(s-1,t)+f(s,t-1), \] with boundary values $f(1,t)=f(s,1)=1$. Also $R(1,t)=R(s,1)=1$ under the convention that $K_1$ is monochromatic. By induction on $s+t$ using (R) and the recursion for $f$, we obtain $R(s,t)\le f(s,t)$. Specializing to $s=t=k$ yields $R(k)\le \binom{2k-2}{k-1}$. $\square$

Lemma 2 (A fully explicit probabilistic lower bound at the $k2^{k/2}$ scale). For every integer $k\ge 3$, \[ R(k) > \left\lfloor \frac{k}{e\sqrt{2}}\,2^{k/2}\right\rfloor. \] Equivalently, there exists a 2-colouring of the edges of $K_n$ with $n=\left\lfloor \frac{k}{e\sqrt{2}}\,2^{k/2}\right\rfloor$ containing no monochromatic copy of $K_k$.

Proof. Fix $n$ and colour each edge of $K_n$ independently red/blue with probability $1/2$ each. For each $k$-subset $S\subseteq [n]$ (vertex set), let $E_S$ be the event that $S$ spans a monochromatic $K_k$. There are exactly two monochromatic colour choices, so \[ \mathbb{P}(E_S)=2\cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}. \] Let $X$ be the number of monochromatic $K_k$ subgraphs. By linearity of expectation, \[ \mathbb{E}[X]=\binom{n}{k} 2^{1-\binom{k}{2}}. \] We will show that for $n=\left\lfloor \frac{k}{e\sqrt{2}}\,2^{k/2}\right\rfloor$ and $k\ge 3$ we have $\mathbb{E}[X]<1$. Then some colouring has $X=0$, implying $R(k)>n$.

To bound $\binom{n}{k}$, use \[ \binom{n}{k} \le \frac{n^k}{k!}. \tag{3} \] We also need a concrete lower bound on $k!$. Claim. For every integer $k\ge 1$, \[ k! \ge \sqrt{2k}\,\left(\frac{k}{e}\right)^k. \tag{4} \] Proof of the claim. The function $\ln x$ is concave on $(0,\infty)$. For each integer $1\le i\le k$, concavity implies that the average value of $\ln x$ on $[i-\tfrac12,i+\tfrac12]$ is at most $\ln i$: \[ \int_{i-1/2}^{i+1/2} \ln x\,dx \le 1\cdot \ln i. \] Summing over $i=1,2,\dots,k$ gives \[ \int_{1/2}^{k+1/2} \ln x\,dx \le \sum_{i=1}^k \ln i = \ln(k!). \] Evaluating the integral, \[ \int_{1/2}^{k+1/2} \ln x\,dx = \left[x\ln x - x\right]_{1/2}^{k+1/2} = (k+\tfrac12)\ln(k+\tfrac12) - (k+\tfrac12) + \tfrac12\ln 2 + \tfrac12. \] Since $\ln(k+\tfrac12)\ge \ln k$ for $k\ge 1$, this is at least \[ (k+\tfrac12)\ln k - (k+\tfrac12) + \tfrac12\ln 2 + \tfrac12 = k\ln k - k + \tfrac12\ln(2k). \] Therefore \[ \ln(k!) \ge k\ln k - k + \tfrac12\ln(2k). \] Exponentiating yields $4$. $\triangle$

Using $3$ and $4$, \[ \mathbb{E}[X]\le 2\cdot \frac{n^k}{k!}\cdot 2^{-\binom{k}{2}} \le 2\cdot \frac{n^k}{\sqrt{2k}(k/e)^k}\cdot 2^{-\binom{k}{2}} = \sqrt{\frac{2}{k}}\,\left(\frac{en}{k}\right)^k 2^{-\binom{k}{2}}. \] Now choose $n\le \frac{k}{e\sqrt{2}}\,2^{k/2}$. Then \[ \left(\frac{en}{k}\right)^k \le \left(\frac{1}{\sqrt{2}}\,2^{k/2}\right)^k = 2^{-k/2} 2^{k^2/2} = 2^{\binom{k}{2}}. \] Substituting gives \[ \mathbb{E}[X] \le \sqrt{\frac{2}{k}}. \] For every $k\ge 3$, $\sqrt{2/k}<1$, hence $\mathbb{E}[X]<1$. Therefore there exists a colouring with $X=0$, i.e. no monochromatic $K_k$. This implies $R(k)>n$. $\square$

FAST REALITY CHECK (small cases / computation). By brute force over all $2^{\binom{n}{2}}$ edge-colourings for $n=5,6$:

• There exists a 2-colouring of $K_5$ with no monochromatic triangle, but none for $K_6$. Hence $R(3)=6$.

(Explicit example for $K_5$: colour the edges of a 5-cycle red and all remaining edges blue.)

VERIFICATION.

• Lemma 1: the recursion (R) is checked vertex-by-vertex and uses only the defining property of $R(s,t)$.
• Lemma 2: the only analytic input is the elementary factorial bound $4$, proved from concavity of $\ln$; all inequalities are explicit and checked for $k\ge 3$.

FINAL. UNRESOLVED.

(i) Strongest proved partial result. A completely explicit constant-factor lower bound holds: $R(k) > \left\lfloor \frac{k}{e\sqrt{2}}2^{k/2}\right\rfloor$ for all $k\ge 3$ (Lemma 2). Also $R(k)\le \binom{2k-2}{k-1}$ (Lemma 1). Thus $\frac{R(k)}{k2^{k/2}}$ is bounded below by $\frac{1}{e\sqrt{2}}+o(1)$, but this does not diverge.

(ii) First gap (crisp). Prove (or disprove) that $R(k)\ge f(k)\,k2^{k/2}$ for some function $f(k)\to\infty$. Equivalently: show that for every fixed $C$ and all large $k$, there exists a 2-colouring of $K_{Ck2^{k/2}}$ with no monochromatic $K_k$.

(iii) Top 3 next moves. 1. Try to push the probabilistic method beyond the first-moment threshold, e.g. prove that with positive probability a random colouring has at most $o(1)$ monochromatic $K_k$ and can be "repaired" to eliminate them while preserving size. 2. Attempt to build explicit constructions (iterative products/stepping-up style) yielding an extra factor in $k$ (or more) over the baseline $k2^{k/2}$. 3. Computationally: implement a SAT/DPLL search for small $k$ to see whether $R(k)/(k2^{k/2})$ is increasing and to look for structural patterns in near-extremal colourings.

(iv) What a minimal counterexample would likely look like. A disproof would require a uniform constant $C$ and an infinite sequence $k\to\infty$ with $R(k)\le Ck2^{k/2}$, i.e. 2-colourings of $K_{\approx Ck2^{k/2}}$ that necessarily force monochromatic $K_k$ at this scale. A proof would require exhibiting colourings on significantly larger $n$ (e.g. $n\ge k^{1+\varepsilon}2^{k/2}$ infinitely often, or stronger).