we-solve (beta)

Math-6068 · mathematics · Mathematics

Erdős Problem #1014

Status Solved · erdosproblems.comLLM status Solved from source status

Statement

Fix an integer $k\ge 3$. For each integer $\ell\ge 1$, let $R(k,\ell)$ be the least integer $n$ such that every (simple, undirected) graph $G$ on $n$ vertices contains either a clique $K_k$ or an independent set of size $\ell$. The problem asks to prove that \[ \lim_{\ell\to\infty} \frac{R(k,\ell+1)}{R(k,\ell)} = 1. \] Equivalently, one wants $R(k,\ell+1)-R(k,\ell)=o(R(k,\ell))$ as $\ell\to\infty$.

Restatement from Math-6068-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-6068-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-6068

Erdős Problem 1014

Statement and result.
For every fixed integer $k\geq3$, \[ \lim_{\ell\to\infty}\frac{R(k,\ell+1)}{R(k,\ell)}=1. \] We reconstruct the dependent-random-choice proof attributed to an internal OpenAI model, proving the auxiliary estimates used here as well. No new Ramsey-number estimate or local Lean verification is claimed.
Two elementary Ramsey estimates.
Use $R(1,\ell)=1$. The neighbourhood/non-neighbourhood argument gives \[ R(a,b)\leq R(a-1,b)+R(a,b-1), \] because a vertex with at least $R(a-1,b)$ neighbours supplies either a clique through that vertex or an independent $b$-set; otherwise its non-neighbours supply a clique or an independent $(b-1)$-set to which it can be added. Induction yields \[ R(a,b)\leq\binom{a+b-2}{a-1},\qquad R(a,\ell+1)=O_a(\ell^{a-1}). \tag{1} \]

We also need \[ R(k,\ell)\gg_k(\ell/\log\ell)^{k/2}. \tag{2} \] Here is an alteration proof. Set \[ M=\left\lfloor\left(\frac{\ell}{100k\log\ell}\right)^{k/2}\right\rfloor, \qquad p=\tfrac12 M^{-2/k}, \] and take the random graph $G(M,p)$. For large $\ell$, $M>\ell$. The expected number of $K_k$'s is at most \[ \frac{M^k}{k!}p^{\binom k2} =\frac{2^{-\binom k2}}{k!}M<M/4. \] In fact Markov's inequality puts the probability of at least $M/2$ such cliques below $1/2$. The expected number of independent $\ell$-sets is at most \[ \binom M\ell(1-p)^{\binom\ell2} \leq\exp\!\left(\ell\log(eM/\ell)-p\ell(\ell-1)/2\right)=o(1). \] To check the last inequality, $\log(eM/\ell)\leq(k/2)\log\ell+1$, whereas $p(\ell-1)/2\geq20k\log\ell$ for sufficiently large $\ell$. Thus some outcome has no independent $\ell$-set and fewer than $M/2$ copies of $K_k$. Delete one vertex from each original clique. The remaining graph has at least $M/2$ vertices, no $K_k$, and no independent $\ell$-set. This proves $2$.

Dependent random choice, with proof.
Let a graph have $N$ vertices and average degree $d$. For positive integers $q,s,m$, there is a set $U$ such that every $s$-subset of $U$ has at least $m$ common neighbours and \[ |U|\geq \frac{d^q}{N^{q-1}} -\binom Ns\left(\frac{m-1}{N}\right)^q. \tag{3} \] Choose $q$ vertices independently and uniformly, allowing repetitions, and let $X$ be their common neighbourhood. Then \[ \mathbb E|X|=\sum_v(d(v)/N)^q\geq d^q/N^{q-1} \] by convexity. Call an $s$-set bad if it has at most $m-1$ common neighbours. Each bad set is contained in $X$ with probability at most $((m-1)/N)^q$. Subtract the number of bad sets contained in $X$ from $|X|$, and take an outcome achieving at least its expectation. Delete one vertex from each bad set in that outcome. The surviving $U$ proves $3$. Deletion cannot introduce a bad subset that was absent before.
Apply this to a critical graph.
Fix $k$, and write \[ s=\lceil k/2\rceil,\quad t=\lfloor k/2\rfloor,\quad q=k^2, \quad N=R(k,\ell+1)-1. \] Choose an $N$-vertex graph $G$ with no $K_k$ and with independence number at most $\ell$. For every vertex $v$, its non-neighbours, excluding $v$, have no independent $\ell$-set. Hence there are at most $R(k,\ell)-1$ of them, and \[ d(v)\geq N-R(k,\ell)=:\Delta. \tag{4} \] Monotonicity is in fact strict here: adjoining an isolated vertex to a critical graph for $R(k,\ell)$ proves $R(k,\ell+1)\geq R(k,\ell)+1$, so $\Delta\geq0$.

Apply $3$ with $m=R(t,\ell+1)$. Its set $U$ cannot contain $K_s$: the common neighbourhood of such a clique has at least $R(t,\ell+1)$ vertices and no independent $(\ell+1)$-set, so it contains $K_t$. The common neighbourhood is disjoint from the original clique, since there are no loops, and the two cliques form $K_k$. Thus \[ |U|\leq R(s,\ell+1)-1. \] Equations $3$--$4$ imply \[ \left(\frac{\Delta}{N}\right)^q \leq\frac{R(s,\ell+1)-1}{N} +\binom Ns\,\frac{(R(t,\ell+1)-1)^q}{N^{q+1}}. \tag{5} \]

Both terms tend to zero.
By $1$--$2$, $N\geq\ell^{k/2-o(1)}$. The first term in $5$ is at most \[ O_k(\ell^{s-1-k/2+o(1)})=o(1), \] since $s-1-k/2\leq-1/2$. The second term is at most a constant times \[ \frac{\ell^{q(t-1)}}{N^{q-s+1}} \leq \ell^{\,q(t-1-k/2)+(k/2)(s-1)+o(1)}=o(1). \] Indeed $t-1-k/2\leq-1$, $s-1\leq k/2$, and $q=k^2$, so the fixed exponent is at most $-3k^2/4$. When $t=1$, the second term is actually zero. It follows that $\Delta/N\to0$. Since $R(k,\ell+1)-R(k,\ell)=\Delta+1$ and $N\to\infty$, we obtain the desired ratio limit.
Attribution and assessment.
The balanced clique split and application to a hypothetical dense critical graph are from On the ratio of $R(k,\ell)$ and $R(k,\ell+1)$, https://cdn.openai.com/pdf/6dc7175d-d9e7-4b8d-96b8-48fe5798cd5b/Ramsey.pdf. See https://www.erdosproblems.com/1014, checked 24 September 2026. The reconstruction supplies the standard probabilistic lower bound and dependent-random-choice lemma rather than assuming them. The conclusion is proved for every fixed $k$; no uniformity for growing $k$ is asserted.
Completion estimate.
COMPLETION: 100%

Go to contribution →

Math-6068-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-6068

FORMAL RESTATEMENT. Fix an integer $k\ge 3$. For each integer $\ell\ge 1$, let $R(k,\ell)$ be the least integer $n$ such that every (simple, undirected) graph $G$ on $n$ vertices contains either a clique $K_k$ or an independent set of size $\ell$. The problem asks to prove that \[ \lim_{\ell\to\infty} \frac{R(k,\ell+1)}{R(k,\ell)} = 1. \] Equivalently, one wants $R(k,\ell+1)-R(k,\ell)=o(R(k,\ell))$ as $\ell\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself says this limit is open even for $k=3$.

ATTACK PLAN. Proof track: $1$ Use the standard Ramsey recursion to relate $R(k,\ell+1)$ and $R(k,\ell)$; try to show the increment is much smaller than $R(k,\ell)$. $2$ Seek a comparison of $R(k-1,\ell)$ with $R(k,\ell)$ for fixed $k$.

Disproof track: Try to force a multiplicative jump $R(k,\ell+1)\ge (1+\varepsilon)R(k,\ell)$ for infinitely many $\ell$ by constructing near-extremal $K_k$-free graphs whose independence number changes abruptly with $\ell$.

WORK.

Lemma 1 (Ramsey recursion). For integers $k,\ell\ge 2$, \[ R(k,\ell) \le R(k-1,\ell) + R(k,\ell-1). \] Proof. Let $n:=R(k-1,\ell)+R(k,\ell-1)$ and let $G$ be any graph on $n$ vertices. Pick a vertex $v\in V(G)$ and let $N(v)$ be its neighborhood and $\overline N(v)$ its non-neighborhood (excluding $v$). Then $|N(v)|+|\overline N(v)|=n-1$. If $|N(v)|\ge R(k-1,\ell)$ then the induced subgraph $G[N(v)]$ contains either a $K_{k-1}$, in which case $G$ contains a $K_k$ using $v$, or an independent set of size $\ell$, which is also independent in $G$. If instead $|N(v)|<R(k-1,\ell)$, then $|\overline N(v)|\ge n-1-(R(k-1,\ell)-1)=R(k,\ell-1)$. In that case, the induced subgraph on $\overline N(v)$ contains either a $K_k$ (hence $G$ does), or an independent set of size $\ell-1$; adjoining $v$ gives an independent set of size $\ell$ in $G$. Thus every graph on $n$ vertices contains a $K_k$ or an independent $\ell$-set, so $R(k,\ell)\le n$. $\square$

Lemma 2 (a conditional reduction to lower parameters). Fix $k\ge 3$. Suppose that as $\ell\to\infty$ both \[ \frac{R(k-1,\ell+1)}{R(k-1,\ell)}\to 1 \qquad\text{and}\qquad \frac{R(k-1,\ell)}{R(k,\ell)}\to 0. \] Then $\displaystyle \frac{R(k,\ell+1)}{R(k,\ell)}\to 1$.

Proof. Monotonicity of Ramsey numbers in the second argument gives $R(k,\ell+1)\ge R(k,\ell)$, hence \[\liminf_{\ell\to\infty}\frac{R(k,\ell+1)}{R(k,\ell)}\ge 1.\] Applying Lemma 1 with $(k,\ell+1)$ gives \[ R(k,\ell+1) \le R(k,\ell) + R(k-1,\ell+1). \] Divide by $R(k,\ell)$: \[ \frac{R(k,\ell+1)}{R(k,\ell)} \le 1 + \frac{R(k-1,\ell+1)}{R(k,\ell)} = 1 + \frac{R(k-1,\ell+1)}{R(k-1,\ell)}\cdot\frac{R(k-1,\ell)}{R(k,\ell)}. \] By the two hypotheses, the product tends to $1\cdot 0=0$, so the right-hand side tends to $1$. Therefore \[\limsup_{\ell\to\infty}\frac{R(k,\ell+1)}{R(k,\ell)}\le 1.\] Together with the $\liminf\ge 1$ this implies the desired limit $=1$. $\square$

FAST REALITY CHECK. A brute-force check for $(k,\ell)=(3,3)$ confirms $R(3,3)=6$. (Enumeration of all graphs on $n\le 6$ vertices shows that $n=5$ is not forced, while $n=6$ is forced.)

VERIFICATION. Lemma 1 uses only the partition of vertices into neighbors/non-neighbors of a fixed vertex and the defining property of Ramsey numbers; all quantifiers are explicit and no extra hypotheses (connectivity, etc.) are used. Lemma 2 is a purely conditional implication; the only inputs are Lemma 1 and monotonicity $R(k,\ell+1)\ge R(k,\ell)$.

FINAL. UNRESOLVED

(i) Strongest proved partial result: Lemma 1 (Ramsey recursion) and Lemma 2 (a clean conditional reduction showing the ratio limit for parameter $k$ would follow from a ratio limit for $k-1$ and from $R(k-1,\ell)=o(R(k,\ell))$).

(ii) First gap (crisp): prove either $R(k-1,\ell)=o(R(k,\ell))$ for fixed $k$ or otherwise show directly that $R(k,\ell+1)-R(k,\ell)=o(R(k,\ell))$.

(iii) Top 3 next moves: 1. Prove quantitative separation $R(k,\ell)\ge \ell^{1+\varepsilon_k}\,R(k-1,\ell)$ (any fixed $\varepsilon_k>0$ would imply $R(k-1,\ell)=o(R(k,\ell))$). 2. Search for a subadditivity/smoothness inequality like $R(k,\ell+t)\le (1+o(1))R(k,\ell)$ for $t=o(\ell)$ via refined recursion. 3. Computationally search (small $\ell$) for whether $R(3,\ell+1)/R(3,\ell)$ ever exhibits large jumps, to guide potential counterexample heuristics.

(iv) Minimal counterexample structure: a fixed $k\ge 3$ and an $\varepsilon>0$ such that infinitely many $\ell$ satisfy $R(k,\ell+1)\ge (1+\varepsilon)R(k,\ell)$; this would require near-extremal $K_k$-free graphs on about $R(k,\ell)$ vertices whose independence number is tightly concentrated around $\ell$.

Go to contribution →