Erdős Problem #1030

Erdős Problem 1030 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

If $R(k,l)$ is the Ramsey number then prove the existence of some $c>0$ such that\[\lim_k \frac{R(k+1,k)}{R(k,k)}> 1+c.\] A problem of Erdős and Sós, who could not even prove whether $R(k+1,k)-R(k,k)>k^c$ for any $c>1$. It is trivial that $R(k+1,k)-R(k,k)\geq k-2$. Burr, Erdős, Faudree, and Schelp [BEFS89] proved\[R(k+1,k)-R(k,k)\geq 2k-5.\]See also [544] for a similar question concerning $R(3,k)$, and [1014] for the general off-diagonal case. References [BEFS89] Burr, S. A. and Erdős, P. and Faudree, R. J. and Schelp, R. H., On the difference between consecutive {R}amsey numbers . Utilitas Math. $1989$, 115--118.

Erdős Problem #1030 --- Solution Attempt

FORMAL RESTATEMENT. For integers $k,\ell\ge 2$, let $R(k,\ell)$ be the smallest $n$ such that every red/blue edge-colouring of $K_n$ contains either a red $K_k$ or a blue $K_\ell$. The problem asks whether there exists a constant $c>0$ such that \[ \liminf_{k\to\infty}\frac{R(k+1,k)}{R(k,k)} > 1+c. \] (Interpreting the problem's "$\lim_k$" as at least a liminf, since existence of a strict limit is not known from the statement.)

QUICK LITERATURE/CONTEXT CHECK. The statement records:

• the trivial bound $R(k+1,k)-R(k,k)\ge k-2$,
• the stronger bound $R(k+1,k)-R(k,k)\ge 2k-5$ due to Burr--Erdős--Faudree--Schelp [BEFS89].

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

ATTACK PLAN. Proof track: show that $R(k+1,k)$ grows at least multiplicatively faster than $R(k,k)$, e.g. by proving a superlinear difference bound $R(k+1,k)-R(k,k)\ge \Omega(R(k,k))$.

Disproof track: attempt to construct colourings showing $R(k+1,k)\le (1+o(1))R(k,k)$, or at least $\liminf$ of the ratio equals $1$.

Here I provide rigorous baseline inequalities and small-$k$ computations.

WORK.

Lemma 1 (An elementary additive lower bound). For every integer $k\ge 2$, \[ R(k+1,k) \ge R(k,k) + (k-1). \] In particular, $R(k+1,k)-R(k,k)\ge k-1$.

Proof. Let $n:=R(k,k)-1$. By definition of $R(k,k)$, there exists a red/blue colouring of the edges of $K_n$ with no red $K_k$ and no blue $K_k$. Fix such a colouring on a vertex set $V$ with $|V|=n$.

We build a colouring on $V\cup W$ where $W$ is a set of $k-1$ new vertices. Colour every edge inside $W$ blue. Colour every edge between $W$ and $V$ red. Keep the original colouring on edges inside $V$. Let $N:=n+(k-1)=R(k,k)+k-2$.

We claim that this colouring of $K_N$ contains neither a red $K_{k+1}$ nor a blue $K_k$.

No blue $K_k$. Any set of $k$ vertices contained entirely in $V$ is not a blue $K_k$ by the defining property of the colouring on $V$. If a set of $k$ vertices contains at least one vertex from $W$, then it also contains at most $k-1$ vertices from $V$. But every edge between $W$ and $V$ is red, so such a $k$-set cannot span a blue $K_k$.

No red $K_{k+1}$. Any red clique can contain at most one vertex from $W$, because edges inside $W$ are blue. So a red $K_{k+1}$ would have to be either entirely inside $V$ (impossible since the colouring on $V$ has no red $K_k$, hence no red $K_{k+1}$), or consist of one vertex from $W$ plus $k$ vertices from $V$. In the latter case, the $k$ vertices from $V$ would need to form a red $K_k$ (since all edges from $W$ to $V$ are red), contradicting the property of the colouring on $V$.

Thus the constructed colouring of $K_N$ avoids red $K_{k+1}$ and blue $K_k$, so $R(k+1,k) > N = R(k,k)+k-2$. Equivalently, $R(k+1,k)\ge R(k,k)+k-1$. $\square$

Lemma 2 (A simple explicit lower bound for $R(k,k)$). For every integer $k\ge 2$, \[ R(k,k) > (k-1)^2. \] Equivalently, $R(k,k)\ge (k-1)^2+1$.

Proof. Let $n:=(k-1)^2$ and partition the $n$ vertices into $k-1$ groups $V_1,\dots,V_{k-1}$ each of size $k-1$. Colour edges inside each group $V_i$ red, and colour edges between distinct groups blue.

Then there is no red $K_k$ because within any group there are only $k-1$ vertices. There is no blue $K_k$ because a blue clique can include at most one vertex from each group (edges inside a group are red), so it has size at most $k-1$. Hence this colouring of $K_n$ avoids both a red and a blue $K_k$, proving $R(k,k)>n$. $\square$

FAST REALITY CHECK (small cases / computation).

• Brute force confirms $R(3,3)=6$.
• Using a DPLL/SAT search for $(4,3)$, there exists a colouring of $K_8$ with no red $K_4$ and no blue $K_3$, but none exists for $K_9$. Thus $R(4,3)=9$. One explicit $K_8$ colouring (red edges listed) avoiding red $K_4$ and blue $K_3$ is: \[\begin{aligned} &\{01,02,03,04,05,12,13,16,17,24,26,35,37,45,46,47,57,67\} \end{aligned}\] (where $ij$ denotes the edge between vertices $i$ and $j$).

For this small case, the ratio is $\frac{R(4,3)}{R(3,3)}=\frac{9}{6}=1.5$.

VERIFICATION.

• Lemma 1: checked that any red clique can have at most one vertex in $W$ because all edges in $W$ are blue, and that any candidate red $K_{k+1}$ would force a red $K_k$ inside $V$.
• Lemma 2: checked both obstructions (red and blue) by counting how many vertices can be taken from each part.
• The small-case $R(4,3)=9$ statement is backed by an exhaustive DPLL/SAT search: it explicitly finds a satisfying assignment for $n=8$ and proves unsatisfiable for $n=9$ under the clauses "no red $K_4$" and "no blue $K_3$".

FINAL. UNRESOLVED.

(i) Strongest proved partial result. An explicit additive separation holds: $R(k+1,k)\ge R(k,k)+k-1$ (Lemma 1), and $R(k,k)\ge (k-1)^2+1$ (Lemma 2). Thus \[ \frac{R(k+1,k)}{R(k,k)} \ge 1 + \frac{k-1}{R(k,k)} \ge 1 + \frac{k-1}{(k-1)^2+1} = 1 + \Theta\!\left(\frac{1}{k}\right), \] which does not give a constant $c>0$.

(ii) First gap (crisp). Prove or disprove: there exists $c>0$ and $k_0$ such that for all $k\ge k_0$, \[R(k+1,k)\ge (1+c)R(k,k).\]

(iii) Top 3 next moves. 1. Strengthen Lemma 1 from an additive gap $\Omega(k)$ to a gap $\Omega(R(k,k))$ (even on a subsequence), e.g. by constructing colourings on $(1+o(1))R(k,k)$ vertices avoiding red $K_{k+1}$ and blue $K_k$. 2. Try to relate $R(k+1,k)$ to off-diagonal asymptotics (e.g. $R(k+1,k)\approx R(k,k)$ would suggest very tight off-diagonal control) and test numerically for small $k$ via SAT. 3. Investigate whether known lower-bound constructions for $R(k,k)$ can be modified to avoid red $K_{k+1}$ without significantly shrinking $n$; formally, target a lemma of the form "from a $(k,k)$-Ramsey colouring on $n$ vertices, build a $(k+1,k)$-Ramsey colouring on $(1+\delta)n$ vertices".

(iv) What a minimal counterexample would likely look like. If the statement is false, one expects an infinite sequence $k\to\infty$ for which there exist colourings on $n\approx (1+o(1))R(k,k)$ vertices that avoid both a red $K_{k+1}$ and a blue $K_k$, forcing $R(k+1,k)/R(k,k)\to 1$ along that sequence.

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,l)$ is the Ramsey number then prove the existence of some $c>0$ such that\[\lim_k \frac{R(k+1,k)}{R(k,k)}> 1+c.\] A problem of Erdős and Sós, who could not even prove whether $R(k+1,k)-R(k,k)>k^c$ for any $c>1$. It is trivial that $R(k+1,k)-R(k,k)\geq k-2$. Burr, Erdős, Faudree, and Schelp [BEFS89] proved\[R(k+1,k)-R(k,k)\geq 2k-5.\]See also [544] for a similar question concerning $R(3,k)$, and [1014] for the general off-diagonal case. References [BEFS89] Burr, S. A. and Erdős, P. and Faudree, R. J. and Schelp, R. H., On the difference between consecutive {R}amsey numbers . Utilitas Math. $1989$, 115--118.

Erdős Problem #1030 --- Solution Attempt

FORMAL RESTATEMENT. For integers $k,\ell\ge 2$, let $R(k,\ell)$ be the smallest $n$ such that every red/blue edge-colouring of $K_n$ contains either a red $K_k$ or a blue $K_\ell$. The problem asks whether there exists a constant $c>0$ such that \[ \liminf_{k\to\infty}\frac{R(k+1,k)}{R(k,k)} > 1+c. \] (Interpreting the problem's "$\lim_k$" as at least a liminf, since existence of a strict limit is not known from the statement.)

QUICK LITERATURE/CONTEXT CHECK. The statement records:

• the trivial bound $R(k+1,k)-R(k,k)\ge k-2$,
• the stronger bound $R(k+1,k)-R(k,k)\ge 2k-5$ due to Burr--Erdős--Faudree--Schelp [BEFS89].

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

ATTACK PLAN. Proof track: show that $R(k+1,k)$ grows at least multiplicatively faster than $R(k,k)$, e.g. by proving a superlinear difference bound $R(k+1,k)-R(k,k)\ge \Omega(R(k,k))$.

Disproof track: attempt to construct colourings showing $R(k+1,k)\le (1+o(1))R(k,k)$, or at least $\liminf$ of the ratio equals $1$.

Here I provide rigorous baseline inequalities and small-$k$ computations.

WORK.

Lemma 1 (An elementary additive lower bound). For every integer $k\ge 2$, \[ R(k+1,k) \ge R(k,k) + (k-1). \] In particular, $R(k+1,k)-R(k,k)\ge k-1$.

Proof. Let $n:=R(k,k)-1$. By definition of $R(k,k)$, there exists a red/blue colouring of the edges of $K_n$ with no red $K_k$ and no blue $K_k$. Fix such a colouring on a vertex set $V$ with $|V|=n$.

We build a colouring on $V\cup W$ where $W$ is a set of $k-1$ new vertices. Colour every edge inside $W$ blue. Colour every edge between $W$ and $V$ red. Keep the original colouring on edges inside $V$. Let $N:=n+(k-1)=R(k,k)+k-2$.

We claim that this colouring of $K_N$ contains neither a red $K_{k+1}$ nor a blue $K_k$.

No blue $K_k$. Any set of $k$ vertices contained entirely in $V$ is not a blue $K_k$ by the defining property of the colouring on $V$. If a set of $k$ vertices contains at least one vertex from $W$, then it also contains at most $k-1$ vertices from $V$. But every edge between $W$ and $V$ is red, so such a $k$-set cannot span a blue $K_k$.

No red $K_{k+1}$. Any red clique can contain at most one vertex from $W$, because edges inside $W$ are blue. So a red $K_{k+1}$ would have to be either entirely inside $V$ (impossible since the colouring on $V$ has no red $K_k$, hence no red $K_{k+1}$), or consist of one vertex from $W$ plus $k$ vertices from $V$. In the latter case, the $k$ vertices from $V$ would need to form a red $K_k$ (since all edges from $W$ to $V$ are red), contradicting the property of the colouring on $V$.

Thus the constructed colouring of $K_N$ avoids red $K_{k+1}$ and blue $K_k$, so $R(k+1,k) > N = R(k,k)+k-2$. Equivalently, $R(k+1,k)\ge R(k,k)+k-1$. $\square$

Lemma 2 (A simple explicit lower bound for $R(k,k)$). For every integer $k\ge 2$, \[ R(k,k) > (k-1)^2. \] Equivalently, $R(k,k)\ge (k-1)^2+1$.

Proof. Let $n:=(k-1)^2$ and partition the $n$ vertices into $k-1$ groups $V_1,\dots,V_{k-1}$ each of size $k-1$. Colour edges inside each group $V_i$ red, and colour edges between distinct groups blue.

Then there is no red $K_k$ because within any group there are only $k-1$ vertices. There is no blue $K_k$ because a blue clique can include at most one vertex from each group (edges inside a group are red), so it has size at most $k-1$. Hence this colouring of $K_n$ avoids both a red and a blue $K_k$, proving $R(k,k)>n$. $\square$

FAST REALITY CHECK (small cases / computation).

• Brute force confirms $R(3,3)=6$.
• Using a DPLL/SAT search for $(4,3)$, there exists a colouring of $K_8$ with no red $K_4$ and no blue $K_3$, but none exists for $K_9$. Thus $R(4,3)=9$. One explicit $K_8$ colouring (red edges listed) avoiding red $K_4$ and blue $K_3$ is: \[\begin{aligned} &\{01,02,03,04,05,12,13,16,17,24,26,35,37,45,46,47,57,67\} \end{aligned}\] (where $ij$ denotes the edge between vertices $i$ and $j$).

For this small case, the ratio is $\frac{R(4,3)}{R(3,3)}=\frac{9}{6}=1.5$.

VERIFICATION.

• Lemma 1: checked that any red clique can have at most one vertex in $W$ because all edges in $W$ are blue, and that any candidate red $K_{k+1}$ would force a red $K_k$ inside $V$.
• Lemma 2: checked both obstructions (red and blue) by counting how many vertices can be taken from each part.
• The small-case $R(4,3)=9$ statement is backed by an exhaustive DPLL/SAT search: it explicitly finds a satisfying assignment for $n=8$ and proves unsatisfiable for $n=9$ under the clauses "no red $K_4$" and "no blue $K_3$".

FINAL. UNRESOLVED.

(i) Strongest proved partial result. An explicit additive separation holds: $R(k+1,k)\ge R(k,k)+k-1$ (Lemma 1), and $R(k,k)\ge (k-1)^2+1$ (Lemma 2). Thus \[ \frac{R(k+1,k)}{R(k,k)} \ge 1 + \frac{k-1}{R(k,k)} \ge 1 + \frac{k-1}{(k-1)^2+1} = 1 + \Theta\!\left(\frac{1}{k}\right), \] which does not give a constant $c>0$.

(ii) First gap (crisp). Prove or disprove: there exists $c>0$ and $k_0$ such that for all $k\ge k_0$, \[R(k+1,k)\ge (1+c)R(k,k).\]

(iii) Top 3 next moves. 1. Strengthen Lemma 1 from an additive gap $\Omega(k)$ to a gap $\Omega(R(k,k))$ (even on a subsequence), e.g. by constructing colourings on $(1+o(1))R(k,k)$ vertices avoiding red $K_{k+1}$ and blue $K_k$. 2. Try to relate $R(k+1,k)$ to off-diagonal asymptotics (e.g. $R(k+1,k)\approx R(k,k)$ would suggest very tight off-diagonal control) and test numerically for small $k$ via SAT. 3. Investigate whether known lower-bound constructions for $R(k,k)$ can be modified to avoid red $K_{k+1}$ without significantly shrinking $n$; formally, target a lemma of the form "from a $(k,k)$-Ramsey colouring on $n$ vertices, build a $(k+1,k)$-Ramsey colouring on $(1+\delta)n$ vertices".

(iv) What a minimal counterexample would likely look like. If the statement is false, one expects an infinite sequence $k\to\infty$ for which there exist colourings on $n\approx (1+o(1))R(k,k)$ vertices that avoid both a red $K_{k+1}$ and a blue $K_k$, forcing $R(k+1,k)/R(k,k)\to 1$ along that sequence.