Erdős Problem #1029

Erdős Problem 1029 --- collection record

PROVENANCE AND STATUS

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

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/1029.tex.

REUSED SOURCE 1

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

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

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.

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