Reused writeup on Math-849 (gpt pro 5.2)

Erdős Problem 555 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

Fix integers $n\ge 2$ and $k\ge 1$. Let $C_{2n}$ denote the (simple) cycle graph on $2n$ vertices.

For a finite simple graph $G$ and an integer $k\ge 1$, define $R(G;k)$ to be the least integer $m$ such that for every map ("$k$-edge-colouring") \[ \chi:E(K_m)\to [k]:=\{1,2,\dots,k\}, \] there exists a set of vertices $U\subseteq V(K_m)$ and a colour $c\in [k]$ such that the subgraph of $K_m$ induced by $U$ contains a copy of $G$ all of whose edges have colour $c$. (Equivalently: some colour class contains a subgraph isomorphic to $G$.)

The problem asks to determine $R(C_{2n};k)$ exactly (or at least its correct asymptotic growth), as a function of $(n,k)$.

Edge cases: - If $k=1$, then $R(C_{2n};1)=2n$ since $K_{2n}$ contains $C_{2n}$. - If $n=2$, then $C_{2n}=C_4\cong K_{2,2}$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records that Erdős gave bounds (for fixed $n$ and large $k$) \[ k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}. \] No further external results are assumed here beyond what is explicitly in the problem file.

3) ATTACK PLAN

Two complementary tracks:

(Proof/upper bounds.) - Relate $C_{2n}$ to a larger bipartite graph such as $K_{n,n}$ (since $C_{2n}\subseteq K_{n,n}$), then use extremal estimates for $K_{n,n}$-free graphs (Kővári--Sós--Turán type) to force a monochromatic $K_{n,n}$, hence a monochromatic $C_{2n}$. - This yields a polynomial upper bound in $k$ (not sharp, but fully provable from scratch).

(Disproof/lower bounds.) - Construct explicit $k$-edge-colourings of $K_m$ with no monochromatic $C_{2n}$, e.g. by decomposing $K_m$ into matchings via 1-factorizations so that every colour class is a matching (hence cycle-free).

4) WORK

PHASE 1 — FAST REALITY CHECK

- $k=1$: $R(C_{2n};1)=2n$. - $n=2$, $k=2$: brute force confirms $R(C_4;2)=6$. A witness colouring on $K_5$ with no monochromatic $C_4$ is: red edges $\{01,02,04,12,13\}$ and blue edges $\{03,14,23,24,34\}$ (vertices $\{0,1,2,3,4\}$). Exhaustive search over all $2^{15}=32768$ 2-colourings of $K_6$ shows every colouring contains a monochromatic $C_4$. Hence $R(C_4;2)=6$.

PHASE 2 — LANDSCAPE (tools and why)

- 1-factorizations / proper edge-colourings: give explicit cycle-free colour classes. - Double counting + convexity: standard extremal method for forbidding $K_{s,t}$. - Extremal numbers $\mathrm{ex}(m,K_{n,n})$: control maximum edges without $K_{n,n}$, hence force $K_{n,n}$ in a dense colour class. - Pigeonhole: pick densest colour class in a $k$-colouring.

Lemma 555.1 (A linear-in-$k$ lower bound via 1-factorizations). Let $n\ge 2$ and $k\ge 1$. Then \[ R(C_{2n};k)\ge \max\{2n,k+1\}, \] and if $k$ is odd then \[ R(C_{2n};k)\ge \max\{2n,k+2\}. \]

Proof. The trivial bound $R(C_{2n};k)\ge 2n$ holds because $K_m$ contains no $C_{2n}$ when $m<2n$.

For the $k$-dependence, we give explicit $k$-edge-colourings with no monochromatic cycle (hence no monochromatic $C_{2n}$).

Case 1: $k$ even. Let $m=k$. Since $m$ is even, the complete graph $K_m$ admits a 1-factorization: its edges can be partitioned into $m-1=k-1$ perfect matchings. Colour each perfect matching with a distinct colour from $\{1,\dots,k-1\}$ (leave colour $k$ unused). Each colour class is a matching, hence contains no cycle of any length. Therefore this is a $k$-colouring of $K_k$ with no monochromatic $C_{2n}$, so $R(C_{2n};k)>k$, i.e. $R(C_{2n};k)\ge k+1$.

Case 2: $k$ odd. Let $m=k+1$, which is even. Then $K_{k+1}$ has a 1-factorization into $m-1=k$ perfect matchings. Colour each matching with a distinct colour from $[k]$. Again each colour class is a matching, hence acyclic, so there is no monochromatic $C_{2n}$. Thus $R(C_{2n};k)>k+1$, i.e. $R(C_{2n};k)\ge k+2$.

Combining with the $2n$ bound gives the claim. $\square$

Lemma 555.2 (Kővári--Sós--Turán bound for $K_{n,n}$). Let $n\ge 2$ and let $G$ be a graph on $m$ vertices with no (not-necessarily-induced) subgraph isomorphic to $K_{n,n}$. Then \[ e(G)\le \frac12\Big((n-1)^{1/n} m^{2-1/n}+(n-1)m\Big). \]

Proof. For an $n$-set $S\subseteq V(G)$, let $c(S)$ denote the number of common neighbours of all vertices in $S$. If $c(S)\ge n$, then $S$ together with any $n$ of its common neighbours forms a $K_{n,n}$, contradicting the hypothesis. Therefore $c(S)\le n-1$ for all $S$.

Double count the set of pairs $(S,v)$ where $S\in\binom{V(G)}{n}$ and $v$ is adjacent to every vertex in $S$. Counting by $S$ gives \[ \sum_{S\in\binom{V(G)}{n}} c(S)\le (n-1)\binom{m}{n}. \tag{1} \] Counting by $v$ gives $\sum_{v\in V(G)}\binom{d(v)}{n}$, since each vertex $v$ contributes one for each $n$-subset of its neighbourhood. Hence \[ \sum_{v\in V(G)}\binom{d(v)}{n}\le (n-1)\binom{m}{n}. \tag{1'} \]

We now lower-bound the left-hand side in terms of the average degree. For an integer $d\ge 0$ we have $\binom{d}{n}=0$ when $d<n$, and for $d\ge n$, \[ \binom{d}{n}=\frac{d(d-1)\cdots(d-n+1)}{n!}\ge \frac{(d-n+1)^n}{n!} \] since each factor $d-j\ge d-n+1$. Thus for every integer $d\ge 0$, \[ \binom{d}{n}\ge \frac{(d-n+1)_+^n}{n!},\qquad (x)_+:=\max\{x,0\}. \] Apply this with $d=d(v)$ and define \[ X_v:=(d(v)-n+1)_+\ge 0. \] Then \[ \sum_{v\in V(G)}\binom{d(v)}{n}\ge \frac{1}{n!}\sum_{v\in V(G)} X_v^n. \] Because $x\mapsto x^n$ is convex on $[0,\infty)$, Jensen's inequality yields \[ \frac{1}{m}\sum_v X_v^n\ge \left(\frac{1}{m}\sum_v X_v\right)^n. \] Moreover $X_v\ge d(v)-n+1$ for each $v$, hence \[ \sum_v X_v\ge \sum_v (d(v)-n+1)=2e(G)-m(n-1). \] Putting these together gives \[ \sum_{v\in V(G)}\binom{d(v)}{n} \ge \frac{m}{n!}\left(\frac{2e(G)}{m}-(n-1)\right)_+^n. \tag{2} \]

Insert $2$ into $1$, and use the bound $\binom{m}{n}\le \frac{m^n}{n!}$ to obtain \[ \frac{m}{n!}\left(\frac{2e(G)}{m}-(n-1)\right)_+^n\le (n-1)\frac{m^n}{n!}. \] Cancel $m/n!$ (for $m\ge 1$) to get \[ \left(\frac{2e(G)}{m}-(n-1)\right)_+^n\le (n-1)m^{n-1}. \] Taking $n$-th roots (both sides are nonnegative once we replace the left by its positive part) yields \[ \frac{2e(G)}{m}-(n-1)\le (n-1)^{1/n} m^{(n-1)/n}. \] Rearranging gives \[ 2e(G)\le (n-1)^{1/n} m^{2-1/n}+(n-1)m, \] which is the desired inequality. $\square$

Lemma 555.3 (A coarse polynomial upper bound for $R(C_{2n};k)$). For fixed $n\ge 2$ and all $k\ge 2$, \[ R(C_{2n};k)\le \left(4(n-1)^{1/n}k\right)^n+1. \]

Proof. Let \[ C:=4(n-1)^{1/n},\qquad m:=\left\lceil (Ck)^n\right\rceil. \] Consider any $k$-edge-colouring of $K_m$. Among the $k$ colours, pick a colour class with the maximum number of edges; call its graph $G$. Then \[ e(G)\ge \frac{1}{k}\binom{m}{2}=\frac{m(m-1)}{2k}. \tag{3} \]

We show that $e(G)$ exceeds the maximum possible number of edges in a $K_{n,n}$-free graph on $m$ vertices, hence $G$ contains a $K_{n,n}$, and therefore contains $C_{2n}$ (since $C_{2n}\subseteq K_{n,n}$).

By Lemma 555.2, if $G$ were $K_{n,n}$-free then \[ e(G)\le \frac12\Big((n-1)^{1/n} m^{2-1/n}+(n-1)m\Big). \tag{4} \] We now show that the right-hand side of $4$ is at most $m^2/(4k)$, while $3$ gives $e(G)>m^2/(4k)$ for $m\ge 3$.

First term: since $m^{1/n}\ge Ck=4(n-1)^{1/n}k$, we have \[ (n-1)^{1/n} m^{2-1/n}=(n-1)^{1/n}\frac{m^2}{m^{1/n}}\le (n-1)^{1/n}\frac{m^2}{4(n-1)^{1/n}k}=\frac{m^2}{4k}. \] Second term: because $m\ge (Ck)^n=4^n(n-1)k^n$, we have \[ (n-1)m\le \frac{m^2}{4k} \] since $(n-1)m\le m\cdot \frac{m}{4k}$ is equivalent to $m\ge 4k(n-1)$, and indeed \[ m\ge 4^n(n-1)k^n\ge 4k(n-1)\quad\text{for }n\ge 2,k\ge 1. \] Therefore the sum in $4$ is at most $\frac12(\frac{m^2}{4k}+\frac{m^2}{4k})=\frac{m^2}{4k}$.

On the other hand, for $m\ge 3$ we have $m-1>m/2$, so \[ \frac{m(m-1)}{2k}>\frac{m^2}{4k}. \] Thus $3$ contradicts $4$, so $G$ is not $K_{n,n}$-free. Hence $G$ contains a $K_{n,n}$ and therefore a $C_{2n}$ in that colour.

This shows that $K_m\to (C_{2n})_k$, i.e. $R(C_{2n};k)\le m\le (Ck)^n+1$. $\square$

5) VERIFICATION

- Lemma 555.1: each colour class in the 1-factorization colouring is a matching, hence acyclic; thus it forbids $C_{2n}$ for all $n\ge 2$. The parity split (odd/even $k$) matches when $K_m$ is 1-factorizable.

- Lemma 555.2: checked the double count identity $\sum_v \binom{d(v)}{n}=\sum_{S\in\binom{V}{n}} c(S)$ and the key implication "$c(S)\ge n$ creates $K_{n,n}$". The Jensen step is valid because $x\mapsto x^n$ is convex on $[0,\infty)$ and we apply it to $(d(v)-n+1)_+$ implicitly (negative values only weaken the lower bound).

- Lemma 555.3: the sufficient conditions $m^{1/n}\ge 4(n-1)^{1/n}k$ and $m\ge 8k(n-1)$ were chosen to make the algebra one-sided with slack; the final bound is therefore correct though far from sharp.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: - Explicit constructions give $R(C_{2n};k)\ge \max\{2n,k+1\}$ for all $k$, and $\ge \max\{2n,k+2\}$ for odd $k$ (Lemma 555.1). - A coarse extremal argument gives $R(C_{2n};k)=O_n(k^n)$ (Lemma 555.3).

(ii) First gap (crisp): Determine the correct asymptotic exponent of $k$ in $R(C_{2n};k)$ (for fixed $n$), i.e. close the gap between the known bounds $k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}$ stated in the problem.

(iii) Top 3 next moves: 1. Prove/derive sharp asymptotics for $\mathrm{ex}(N,C_{2n})$ and insert into the standard "densest colour class" argument to improve the upper bound. 2. Build improved lower-bound colourings using $C_{2n}$-free pseudorandom graphs in each colour class (beyond matchings) to push $m$ above linear in $k$. 3. Compute exact values for small $(n,k)$ via SAT/backtracking to guess the true exponent pattern and identify tight constructions.

(iv) Minimal counterexample structure: A smallest $(n,k)$ for which conjectured asymptotics/exponents fail would correspond to a $k$-colouring of $K_m$ in which every colour class is $C_{2n}$-free yet globally dense; likely each colour class resembles an extremal $C_{2n}$-free graph (bipartite/pseudorandom) with edge density about $m^{1-1/n}$.

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.