Erdős Problem #554

Erdős Problem 554 --- collection record

PROVENANCE AND STATUS

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

REUSED SOURCE 1

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that \[ \lim_{k\to \infty} \frac{R(C_{2n+1};k)}{R(K_3;k)} =0 \] for any $n\ge 2$.

This is open even for $n=2$ (i.e. for $C_5$).

1) “FORMAL RESTATEMENT”

For a fixed graph $G$ and integer $k\ge 1$, let $R(G;k)$ be the smallest $m$ such that every $k$-edge-colouring of $K_m$ contains a monochromatic copy of $G$.

Fix $n\ge 2$. The problem asks to prove \[ \lim_{k\to\infty} \frac{R(C_{2n+1};k)}{R(K_3;k)} = 0. \] The problem file states this is open even for $n=2$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The only context given is that the claim is open even for $C_5$. I will therefore only prove elementary bounds and structural lemmas, and then state the precise gap.

3) “ATTACK PLAN”

To prove the limit is $0$, one needs an upper bound on $R(C_{2n+1};k)$ and a lower bound on $R(K_3;k)$ whose ratio tends to infinity.

I can give an explicit construction showing both Ramsey numbers exceed $2^k$ (so this does not separate them), and I can give very coarse upper bounds via clique Ramsey numbers. These are far from sufficient to prove the stated limit.

4) “WORK”

Lemma 1 (A $k$-colouring of $K_{2^k}$ with no monochromatic triangle). For each $k\ge 1$, there is a $k$-edge-colouring of $K_{2^k}$ with no monochromatic $K_3$. In particular, \[ R(K_3;k) > 2^k. \]

Proof. Let the vertex set be $\{0,1\}^k$ (binary strings of length $k$), so there are $2^k$ vertices. For two distinct vertices $x\neq y$, define the colour of the edge $xy$ to be the least index $i\in\{1,\dots,k\}$ for which $x_i\neq y_i$.

Suppose for contradiction that there is a monochromatic triangle with vertices $a,b,c$ and all three edges coloured $i$. Then for each pair among $\{a,b,c\}$, the first coordinate where the two vertices differ is exactly $i$. In particular, all three vertices agree in coordinates $1,2,\dots,i-1$. Now look at the $i$th bits $a_i,b_i,c_i\in\{0,1\}$. Among three bits, two are equal; say $a_i=b_i$. Then $a$ and $b$ do not differ at coordinate $i$, so their first differing coordinate is strictly greater than $i$, contradicting that the edge $ab$ has colour $i$. Thus there is no monochromatic triangle.

Therefore this is a $k$-colouring of $K_{2^k}$ without a monochromatic $K_3$, implying $R(K_3;k)>2^k$. $\square$

Lemma 2 (The same colouring forbids every monochromatic odd cycle). In the colouring from Lemma 1, for each fixed colour $i$, the monochromatic graph of colour $i$ is bipartite, hence contains no odd cycle. In particular, for every $n\ge 2$, \[ R(C_{2n+1};k) > 2^k. \]

Proof. Fix a colour $i$. Every edge of colour $i$ joins two vertices that differ at coordinate $i$ (by definition). Therefore all colour-$i$ edges go between the two vertex classes \[ A:=\{x\in\{0,1\}^k : x_i=0\},\qquad B:=\{x\in\{0,1\}^k : x_i=1\}. \] Hence the colour-$i$ graph is bipartite. Bipartite graphs contain no odd cycles, so in particular no $C_{2n+1}$. Thus the colouring has no monochromatic $C_{2n+1}$, proving $R(C_{2n+1};k)>2^k$. $\square$

Lemma 3 (Trivial upper bound via cliques). For every $n\ge 2$ and $k\ge 1$, \[ R(C_{2n+1};k) \le R(K_{2n+1};k). \]

Proof. A complete graph $K_{2n+1}$ contains $C_{2n+1}$ as a subgraph (take a Hamilton cycle). Therefore any monochromatic $K_{2n+1}$ yields a monochromatic $C_{2n+1}$. Hence the minimal $m$ forcing a monochromatic $C_{2n+1}$ is at most the minimal $m$ forcing a monochromatic $K_{2n+1}$. $\square$

5) “VERIFICATION”

Fast reality check (computer verification of Lemma 1 for small $k$): - For $k=1$, $K_{2}$ has no triangle, so the construction vacuously works. - For $k=2,3,4$, a direct programmatic check on the construction on $2^k$ vertices confirms there is no monochromatic triangle.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1 and 2 give explicit lower bounds $R(K_3;k)>2^k$ and $R(C_{2n+1};k)>2^k$ for every fixed $n\ge 2$. Lemma 3 gives the trivial upper bound $R(C_{2n+1};k)\le R(K_{2n+1};k)$.

(ii) First gap (crisp): Prove a separation between the growth rates of $R(C_{2n+1};k)$ and $R(K_3;k)$ strong enough to imply $R(C_{2n+1};k)=o(R(K_3;k))$ as $k\to\infty$. With only the shared lower bound $>2^k$ and trivial clique upper bounds, the ratio is not controlled.

(iii) Top 3 next moves: 1. Improve lower bounds for $R(K_3;k)$: find constructions or counting arguments showing $R(K_3;k)$ grows super-exponentially in $k$ (beyond $2^k$), in a way that can be compared to known/derived upper bounds for odd cycles. 2. Improve upper bounds for $R(C_{2n+1};k)$: exploit the fixed cycle structure (rather than bounding by cliques) to get $R(C_{2n+1};k)\le \exp(o(k\log k))$ or similarly, and then compare to the best available lower bounds for $R(K_3;k)$. 3. Small-$k$ experiments: compute or bound $R(C_{2n+1};k)$ and $R(K_3;k)$ for small $k$ and $n=2,3$ to look for structural patterns in extremal colourings.

(iv) Minimal counterexample structure: A counterexample to the limit statement would amount to an infinite sequence of integers $k_j\to\infty$ such that $R(C_{2n+1};k_j)$ is bounded below by a positive constant multiple of $R(K_3;k_j)$. Equivalently, one would need $k_j$-colourings of $K_{m}$ with $m$ close to $R(K_3;k_j)$ that still avoid monochromatic $C_{2n+1}$, showing odd-cycle avoidance can persist nearly as long as triangle avoidance.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that \[ \lim_{k\to \infty} \frac{R(C_{2n+1};k)}{R(K_3;k)} =0 \] for any $n\ge 2$.

This is open even for $n=2$ (i.e. for $C_5$).

1) “FORMAL RESTATEMENT”

For a fixed graph $G$ and integer $k\ge 1$, let $R(G;k)$ be the smallest $m$ such that every $k$-edge-colouring of $K_m$ contains a monochromatic copy of $G$.

Fix $n\ge 2$. The problem asks to prove \[ \lim_{k\to\infty} \frac{R(C_{2n+1};k)}{R(K_3;k)} = 0. \] The problem file states this is open even for $n=2$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The only context given is that the claim is open even for $C_5$. I will therefore only prove elementary bounds and structural lemmas, and then state the precise gap.

3) “ATTACK PLAN”

To prove the limit is $0$, one needs an upper bound on $R(C_{2n+1};k)$ and a lower bound on $R(K_3;k)$ whose ratio tends to infinity.

I can give an explicit construction showing both Ramsey numbers exceed $2^k$ (so this does not separate them), and I can give very coarse upper bounds via clique Ramsey numbers. These are far from sufficient to prove the stated limit.

4) “WORK”

Lemma 1 (A $k$-colouring of $K_{2^k}$ with no monochromatic triangle). For each $k\ge 1$, there is a $k$-edge-colouring of $K_{2^k}$ with no monochromatic $K_3$. In particular, \[ R(K_3;k) > 2^k. \]

Proof. Let the vertex set be $\{0,1\}^k$ (binary strings of length $k$), so there are $2^k$ vertices. For two distinct vertices $x\neq y$, define the colour of the edge $xy$ to be the least index $i\in\{1,\dots,k\}$ for which $x_i\neq y_i$.

Suppose for contradiction that there is a monochromatic triangle with vertices $a,b,c$ and all three edges coloured $i$. Then for each pair among $\{a,b,c\}$, the first coordinate where the two vertices differ is exactly $i$. In particular, all three vertices agree in coordinates $1,2,\dots,i-1$. Now look at the $i$th bits $a_i,b_i,c_i\in\{0,1\}$. Among three bits, two are equal; say $a_i=b_i$. Then $a$ and $b$ do not differ at coordinate $i$, so their first differing coordinate is strictly greater than $i$, contradicting that the edge $ab$ has colour $i$. Thus there is no monochromatic triangle.

Therefore this is a $k$-colouring of $K_{2^k}$ without a monochromatic $K_3$, implying $R(K_3;k)>2^k$. $\square$

Lemma 2 (The same colouring forbids every monochromatic odd cycle). In the colouring from Lemma 1, for each fixed colour $i$, the monochromatic graph of colour $i$ is bipartite, hence contains no odd cycle. In particular, for every $n\ge 2$, \[ R(C_{2n+1};k) > 2^k. \]

Proof. Fix a colour $i$. Every edge of colour $i$ joins two vertices that differ at coordinate $i$ (by definition). Therefore all colour-$i$ edges go between the two vertex classes \[ A:=\{x\in\{0,1\}^k : x_i=0\},\qquad B:=\{x\in\{0,1\}^k : x_i=1\}. \] Hence the colour-$i$ graph is bipartite. Bipartite graphs contain no odd cycles, so in particular no $C_{2n+1}$. Thus the colouring has no monochromatic $C_{2n+1}$, proving $R(C_{2n+1};k)>2^k$. $\square$

Lemma 3 (Trivial upper bound via cliques). For every $n\ge 2$ and $k\ge 1$, \[ R(C_{2n+1};k) \le R(K_{2n+1};k). \]

Proof. A complete graph $K_{2n+1}$ contains $C_{2n+1}$ as a subgraph (take a Hamilton cycle). Therefore any monochromatic $K_{2n+1}$ yields a monochromatic $C_{2n+1}$. Hence the minimal $m$ forcing a monochromatic $C_{2n+1}$ is at most the minimal $m$ forcing a monochromatic $K_{2n+1}$. $\square$

5) “VERIFICATION”

Fast reality check (computer verification of Lemma 1 for small $k$): - For $k=1$, $K_{2}$ has no triangle, so the construction vacuously works. - For $k=2,3,4$, a direct programmatic check on the construction on $2^k$ vertices confirms there is no monochromatic triangle.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1 and 2 give explicit lower bounds $R(K_3;k)>2^k$ and $R(C_{2n+1};k)>2^k$ for every fixed $n\ge 2$. Lemma 3 gives the trivial upper bound $R(C_{2n+1};k)\le R(K_{2n+1};k)$.

(ii) First gap (crisp): Prove a separation between the growth rates of $R(C_{2n+1};k)$ and $R(K_3;k)$ strong enough to imply $R(C_{2n+1};k)=o(R(K_3;k))$ as $k\to\infty$. With only the shared lower bound $>2^k$ and trivial clique upper bounds, the ratio is not controlled.

(iii) Top 3 next moves: 1. Improve lower bounds for $R(K_3;k)$: find constructions or counting arguments showing $R(K_3;k)$ grows super-exponentially in $k$ (beyond $2^k$), in a way that can be compared to known/derived upper bounds for odd cycles. 2. Improve upper bounds for $R(C_{2n+1};k)$: exploit the fixed cycle structure (rather than bounding by cliques) to get $R(C_{2n+1};k)\le \exp(o(k\log k))$ or similarly, and then compare to the best available lower bounds for $R(K_3;k)$. 3. Small-$k$ experiments: compute or bound $R(C_{2n+1};k)$ and $R(K_3;k)$ for small $k$ and $n=2,3$ to look for structural patterns in extremal colourings.

(iv) Minimal counterexample structure: A counterexample to the limit statement would amount to an infinite sequence of integers $k_j\to\infty$ such that $R(C_{2n+1};k_j)$ is bounded below by a positive constant multiple of $R(K_3;k_j)$. Equivalently, one would need $k_j$-colourings of $K_{m}$ with $m$ close to $R(K_3;k_j)$ that still avoid monochromatic $C_{2n+1}$, showing odd-cycle avoidance can persist nearly as long as triangle avoidance.