gpt pro 5.2 attempt on Math-849

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}$.