we-solve (beta)

Math-945-A1 · revision r1 · on Math-945

Reused writeup on Math-945 (gpt pro 5.2)

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 812 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. Erdos Problem #812
  5. FORMAL RESTATEMENT.
  6. QUICK LITERATURE/CONTEXT CHECK.
  7. ATTACK PLAN.
  8. WORK.
  9. VERIFICATION.
  10. FINAL.
  11. COMPLETION ESTIMATE

Erdős Problem 812 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Erdos Problem #812

FORMAL RESTATEMENT.
Let $R(n)$ denote the diagonal Ramsey number: the least integer $N$ such that every red/blue colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $K_n$.

The problem asks whether there exists a constant $c>0$ such that for all sufficiently large integers $n$, \[ \frac{R(n+1)}{R(n)} \ge 1+c, \] and whether one has the growth lower bound \[ R(n+1)-R(n) \gg n^2, \] (i.e. $R(n+1)-R(n) \ge C n^2$ for some absolute $C>0$ and all sufficiently large $n$).

QUICK LITERATURE/CONTEXT CHECK.
The problem statement records that Burr--Erdős--Faudree--Schelp proved $R(n+1)-R(n)\ge 4n-8$ for $n\ge2$, and that a lower bound cited as "[165]" implies $R(n+2)-R(n)\gg n^{2-o(1)}$. I do not use any results not already stated in the problem text.
ATTACK PLAN.
Proof track: try to force a multiplicative jump $R(n+1)\ge (1+c)R(n)$ by a structural argument on minimal Ramsey graphs or by a density increment in extremal colourings; in lieu of that, establish unconditional (weaker) inequalities that constrain possible behaviour of ratios/differences.

Disproof track: attempt to build colourings on $N$ vertices avoiding monochromatic $K_n$ but only barely failing for $K_{n+1}$, in order to keep $R(n+1)/R(n)\to 1$ or $R(n+1)-R(n)=o(n^2)$. Without further input, this seems to require deep constructions.

WORK.
Lemma 812.1 (explicit linear lower bound). For every integer $n\ge 3$, \[ R(n) \ge 2n-1. \] Proof. We exhibit, for each $n\ge3$, a red/blue colouring of the edges of $K_{2n-2}$ with no monochromatic $K_n$. Partition the vertex set into two parts $V_1,V_2$ of size $n-1$ each. Colour all edges between $V_1$ and $V_2$ red, and colour all edges inside $V_1$ and inside $V_2$ blue.

Any red clique can use at most one vertex from each part, because there are no red edges inside a part; hence the red graph is bipartite and contains no red $K_3$, and in particular no red $K_n$. Any blue clique is contained entirely in $V_1$ or entirely in $V_2$ (since all cross-edges are red), so its size is at most $n-1$, hence there is no blue $K_n$. Thus $K_{2n-2}$ admits a colouring with no monochromatic $K_n$, so by definition $R(n)>2n-2$, i.e. $R(n)\ge 2n-1$. $\square$

Lemma 812.2 (the case $n=3$: $R(3)=6$). Every red/blue colouring of $E(K_6)$ contains a monochromatic triangle, and there exists a red/blue colouring of $E(K_5)$ containing no monochromatic triangle. Consequently $R(3)=6$.

Proof (existence on $5$ vertices). Label the vertices $1,2,3,4,5$. Colour the cycle edges \[(1,2),(2,3),(3,4),(4,5),(5,1) \] red, and colour the remaining edges blue. Any triangle in $K_5$ either contains two consecutive edges of the $5$-cycle (hence has exactly two red edges and one blue), or contains at most one cycle edge (hence has at most one red edge and at least two blue). In either case the triangle is not monochromatic. Thus there is a $2$-colouring of $K_5$ with no monochromatic triangle.

Proof (forcing on $6$ vertices). Consider any red/blue colouring of the edges of $K_6$, and fix a vertex $v$. Among the $5$ edges incident to $v$, at least $3$ have the same colour by the pigeonhole principle. Assume without loss of generality that $v$ is joined by red edges to three distinct vertices $a,b,c$. If any of the edges among $\{a,b,c\}$ is red, then together with $v$ it forms a red triangle. If none of the edges among $\{a,b,c\}$ is red, then all three edges $(a,b),(b,c),(a,c)$ are blue, forming a blue triangle. In all cases a monochromatic triangle exists. Therefore every colouring of $K_6$ has a monochromatic triangle, while some colouring of $K_5$ avoids them, so $R(3)=6$. $\square$

FAST REALITY CHECK (exact computation for $n=3$). I exhaustively enumerated all $2^{\binom{6}{2}}=2^{15}=32768$ red/blue edge-colourings of $K_6$ and confirmed that none avoids monochromatic triangles, and also confirmed that $K_5$ has at least one triangle-avoiding colouring (the $5$-cycle construction above).

VERIFICATION.
Lemma 812.1: the red graph is complete bipartite $K_{n-1,n-1}$, hence contains no triangle, so certainly no $K_n$ for $n\ge3$; the blue graph is the disjoint union of two cliques of size $n-1$, so contains no $K_n$. Both checks use only the colouring definition.

Lemma 812.2: for the $5$-cycle colouring, any triangle uses either $0,1,2$ cycle edges; it cannot use $3$ because the $5$-cycle has no triangles. Thus no monochromatic triangle occurs. For $K_6$, the pigeonhole step gives three same-colour neighbours; checking the two cases among $a,b,c$ yields a monochromatic triangle.

FINAL.
UNRESOLVED.
  1. (i) The strongest proved partial results here are: (a) $R(n)\ge 2n-1$ for all $n\ge3$ (Lemma 812.1), and (b) $R(3)=6$ (Lemma 812.2). In particular, $\frac{R(n+1)}{R(n)} \ge \frac{2(n+1)-1}{2n-1}=1+\frac{2}{2n-1}$ holds for $n\ge3$, which tends to $1$.
  2. (ii) First gap: prove or refute the existence of an absolute $c>0$ and $n_0$ such that $R(n+1)\ge (1+c)R(n)$ for all $n\ge n_0$.
  3. (iii) Top 3 next moves: $1$ analyze "near-extremal" colourings on $R(n+1)-1$ vertices to see whether they must contain many monochromatic $K_n$ that could be extended; $2$ attempt a density increment: show that any colouring avoiding $K_{n+1}$ must have a large subset where one colour has unusually low $K_n$-density, contradicting known lower bounds; $3$ computationally search for small $n$ for which $R(n+1)/R(n)$ is especially small using best-known constructions (as a guide for disproof attempts).
  4. (iv) A minimal counterexample to the ratio claim would be an infinite sequence $n_j\to\infty$ with colourings of $K_{R(n_j+1)-1}$ avoiding monochromatic $K_{n_j+1}$ but having $R(n_j+1) \le (1+o(1))R(n_j)$; such colourings would need to be highly "efficient" in suppressing $K_{n_j+1}$ while only barely increasing the Ramsey threshold.

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.