we-solve (beta)

Math-846-A1 · revision r1 · on Math-846

Reused writeup on Math-846 (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 544 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. COMPLETION ESTIMATE

Erdős Problem 544 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT. Let $R(3,k)$ denote the classical Ramsey number: the smallest integer $n$ such that every graph on $n$ vertices contains either a triangle $K_3$ or an independent set of size $k$. The problem asks to show \[ R(3,k+1)-R(3,k)\to\infty\quad (k\to\infty), \] and also to prove or disprove the stronger claim \[ R(3,k+1)-R(3,k)=o(k). \]

QUICK LITERATURE/CONTEXT CHECK. No external results are used here. I provide only elementary bounds and sanity checks.

ATTACK PLAN. 1) Reprove the standard recursion upper bound for $R(3,k)$ and an elementary construction-based lower bound. 2) Use these to understand what they imply (and do not imply) about first differences. 3) Verify the constructions in small cases computationally (triangle-freeness and independence number).

WORK. Fast reality check (cycle construction verification). For each $k$ from $3$ to $8$, I verified by a short script that the cycle graph $C_{2k-2}$ is triangle-free and has independence number $k-1$. This supports the lower bound Lemma 544.2 below.

Lemma 544.1 (standard recursion upper bound). For $k\ge 2$, \[ R(3,k)\le R(3,k-1)+k. \] In particular, $R(3,k)\le \frac{k(k+1)}{2}$ for all $k\ge 2$.

Proof. Let $n=R(3,k-1)+k$ and let $G$ be any graph on $n$ vertices. Pick a vertex $v$. Let $N(v)$ be its neighbor set and $\overline N(v)$ its non-neighbor set (excluding $v$ itself). Then $|N(v)|+|\overline N(v)|=n-1=R(3,k-1)+k-1$. If $|N(v)|\ge R(2,k)=k$, then $N(v)$ contains an independent set of size $k$ in the complement graph; equivalently, either $N(v)$ contains an edge (which together with $v$ forms a triangle) or $N(v)$ contains an independent set of size $k$ in $G$. More directly for $R(3,k)$, we use the standard Ramsey argument: If $|N(v)|\ge R(2,k)=k$, then either $N(v)$ contains an edge, forming a triangle with $v$, or else $N(v)$ itself is an independent set of size $k$. So in this case $G$ contains a triangle or an independent $k$-set.

Otherwise $|N(v)|\le k-1$, hence $|\overline N(v)|\ge R(3,k-1)$. By definition of $R(3,k-1)$, the induced subgraph on $\overline N(v)$ contains either a triangle (which is also a triangle in $G$) or an independent set of size $k-1$. In the latter case, adding $v$ (which has no edges to $\overline N(v)$) yields an independent set of size $k$. Thus every graph on $n$ vertices has a triangle or an independent $k$-set, proving $R(3,k)\le R(3,k-1)+k$. Summing this inequality from $2$ up to $k$ and using $R(3,2)=3$ gives $R(3,k)\le k(k+1)/2$. $\square$

Lemma 544.2 (elementary lower bound via cycles). For $k\ge 2$, \[ R(3,k)\ge 2k-1. \]

Proof. Consider the cycle graph $C_{2k-2}$ on $2k-2$ vertices. A cycle has no triangles, so $C_{2k-2}$ is triangle-free. Its independence number is $k-1$: in an even cycle, the maximum independent set consists of every other vertex, giving size $(2k-2)/2=k-1$, and no independent set can be larger because any independent set contains at most one vertex from each edge-pair. Therefore there exists a triangle-free graph on $2k-2$ vertices with no independent set of size $k$. By the definition of $R(3,k)$, this implies $R(3,k)>2k-2$, hence $R(3,k)\ge 2k-1$. $\square$

VERIFICATION. The proof of Lemma 544.1 is the standard vertex-neighborhood recursion specialized to $(3,k)$. Lemma 544.2 was computationally checked for $k=3,\dots,8$ by computing independence numbers of $C_{2k-2}$.

FINAL.\;UNRESOLVED.

  • (i) Strongest proved partial result. Elementary bounds: \[2k-1\le R(3,k)\le \frac{k(k+1)}{2}. \] These do not resolve the growth of the first difference $R(3,k+1)-R(3,k)$.
  • (ii) First gap (crisp statement). Prove a lower bound on $R(3,k+1)-R(3,k)$ that tends to infinity with $k$, i.e. find an explicit function $g(k)\to\infty$ such that $R(3,k+1)\ge R(3,k)+g(k)$ for all sufficiently large $k$.
  • (iii) Top 3 next moves.
    • Study extremal triangle-free graphs with bounded independence number (Ramsey graphs): relate $R(3,k)-1$ to the maximum $n$ for which there exists triangle-free $G$ on $n$ vertices with $\alpha(G)\le k-1$. Any method that forces $n$ to increase by $\omega(1)$ when $k$ increases by $1$ would prove the first claim.
    • Attempt to prove an approximate convexity/smoothness property for $R(3,k)$ (e.g. $R(3,k+1)+R(3,k-1)\ge 2R(3,k)+\omega(1)$), which would imply increasing differences.
    • Computationally: for moderate $k$ (where exact Ramsey numbers are known by computation), examine the empirical behavior of differences to guess the correct scale for the two questions.
  • (iv) Minimal counterexample structure to look for. If $R(3,k+1)-R(3,k)$ failed to grow, one would need infinitely many $k$ for which there exists a triangle-free graph on $R(3,k)-1$ vertices with independence $k-1$ that cannot be extended (by adding many vertices) while keeping triangle-free and keeping independence $\le k$. Understanding such "rigid" extremal Ramsey graphs is a plausible route to either proving or disproving divergence of the difference.

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.