we-solve (beta)

Math-852-A1 · revision r1 · on Math-852

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

Erdős Problem 560 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

For a graph $G$, the (2-colour) size Ramsey number $\hat R(G)$ is the least integer $m$ such that there exists a (finite simple) graph $H$ with $m$ edges satisfying: for every red/blue colouring of $E(H)$, the graph $H$ contains a monochromatic copy of $G$. We write this property as $H\to (G)_2$.

The problem asks to determine $\hat R(K_{n,n})$ for the complete bipartite graph with equal parts of size $n$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records known bounds for $n\ge 6$: \[ \frac{1}{60}n^2 2^n < \hat R(K_{n,n}) < \frac{3}{2}n^3 2^n. \] No external improvements are assumed here.

3) ATTACK PLAN

Provide fully proved baseline bounds: - Trivial lower bound from the fact $H$ must contain an uncoloured copy of $K_{n,n}$. - Trivial upper bound using the usual Ramsey number $R(K_{n,n};2)$ by taking $H=K_{R(K_{n,n};2)}$.

Also sanity-check the smallest values (e.g. $n=1,2$).

4) WORK

PHASE 1 — FAST REALITY CHECK

- $n=1$: $K_{1,1}$ is a single edge, so $\hat R(K_{1,1})=1$ (take $H$ to be one edge). - $n=2$: $K_{2,2}\cong C_4$. Since $R(C_4;2)=6$ (Problem 555), taking $H=K_6$ gives $\hat R(K_{2,2})\le \binom{6}{2}=15$.

Lemma 560.1 (Trivial edge-count lower bound). For every graph $G$, $\hat R(G)\ge |E(G)|$. In particular, \[ \hat R(K_{n,n})\ge n^2. \]

Proof. Let $H$ be any graph with $H\to (G)_2$. Consider the monochromatic colouring where every edge of $H$ is coloured red. Then $H$ must contain a red copy of $G$, i.e. $H$ must contain $G$ as an (uncoloured) subgraph. Therefore $|E(H)|\ge |E(G)|$. Taking the minimum over all such $H$ gives $\hat R(G)\ge |E(G)|$. For $G=K_{n,n}$, $|E(G)|=n^2$. $\square$

Lemma 560.2 (Upper bound via the usual Ramsey number). For every graph $G$, \[ \hat R(G)\le \binom{R(G;2)}{2}. \] In particular, \[ \hat R(K_{n,n})\le \binom{R(K_{n,n};2)}{2}. \]

Proof. Let $R:=R(G;2)$, so by definition every red/blue colouring of $E(K_R)$ contains a monochromatic copy of $G$. Take $H:=K_R$, which has $\binom{R}{2}$ edges. Then $H\to (G)_2$, so by the definition of size Ramsey number, \[ \hat R(G)\le |E(H)|=\binom{R}{2}. \] Applying this with $G=K_{n,n}$ gives the stated bound. $\square$

5) VERIFICATION

- Lemma 560.1: the all-red colouring is a legitimate 2-colouring; the definition of $\hat R(G)$ requires a monochromatic $G$ in every such colouring, forcing $G\subseteq H$.

- Lemma 560.2: the definition of $R(G;2)$ is exactly that $K_{R}$ arrows $G$ in 2 colours, so taking $H=K_R$ is valid.

- Reality check $n=1$ is immediate; for $n=2$ the computed $R(C_4;2)=6$ implies the stated upper bound 15.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: - Always $n^2\le \hat R(K_{n,n})\le \binom{R(K_{n,n};2)}{2}$ (Lemmas 560.1–560.2). - Explicit small case: $\hat R(K_{2,2})\le 15$ via $K_6$.

(ii) First gap (crisp): Determine the correct order of magnitude (and ideally asymptotic constant factors) of $\hat R(K_{n,n})$; in particular, explain/prove the exponential-in-$n$ growth $\\sim n^{\\Theta(1)}2^n$ suggested by the bounds in the problem statement.

(iii) Top 3 next moves: 1. Attempt to reproduce the lower bound construction (or a simpler version) showing $\hat R(K_{n,n})\ge c n^2 2^n$ by probabilistic methods on sparse host graphs. 2. Attempt to build an explicit host graph $H$ with $O(n^3 2^n)$ edges that forces monochromatic $K_{n,n}$ under any 2-colouring, possibly using expansion or containers. 3. Compute $\hat R(K_{n,n})$ for $n=2,3$ via exhaustive search/SAT to guess the exact small values and identify extremal host graph shapes.

(iv) Minimal counterexample structure: A minimal host graph $H$ beating the $n^2 2^n$ scale would likely be sparse but highly structured (e.g. bounded degree with good expansion) so that any red/blue colouring creates a large monochromatic biclique. Conversely, a minimal colouring avoiding $K_{n,n}$ on a candidate host graph would likely be pseudorandom with each colour class near the $K_{n,n}$-free extremal 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.