/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtil
public import FormalConjectures.ErdosProblems.«183»Erdős Problem 554
References:
[Er81c] Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885 (1981), 9-17.
[BoEr73] Bondy, J. A. and Erdős, P., Ramsey numbers for cycles in graphs. J. Combin. Theory Ser. B 14 (1973), 46-54.
[ErGr75] Erdős, P. and Graham, R. L., On partition theorems for finite graphs. Infinite and finite sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. János Bolyai 10 (1975), 515-527.
[DaJo17] Day, A. N. and Johnson, J. R., Multicolour Ramsey numbers of odd cycles. J. Combin. Theory Ser. B 124 (2017), 56-63. arXiv:1602.07607
[JeSk21] Jenssen, M. and Skokan, J., Exact Ramsey numbers of odd cycles via nonlinear optimisation. Adv. Math. 376 (2021), Paper No. 107444. arXiv:1608.05705
[ACJMR26] Axenovich, M., Cames van Batenburg, W., Janzer, O., Michel, L. and Rundström, M., An improved upper bound for the multicolour Ramsey number of odd cycles. J. Combin. Theory Ser. B 179 (2026), 293-298. arXiv:2510.17981 doi:10.1016/j.jctb.2026.04.005
@[expose] public sectionopen Filter SimpleGraphopen scoped Topologynamespace Erdos554
$R_k(K_3)$ agrees with Erdos183.multicolourTriangleRamsey: a colouring has a monochromatic
triangle exactly when it is not $3$-clique-free.
@[category test, AMS 5]
theorem multicolourGraphRamsey_completeGraph_three (k : ℕ) :
multicolourGraphRamsey k (completeGraph (Fin 3)) = Erdos183.multicolourTriangleRamsey k := k:ℕ⊢ multicolourGraphRamsey k (completeGraph (Fin 3)) = Erdos183.multicolourTriangleRamsey k
All goals completed! 🐙The cycle $C_3$ is the triangle $K_3$, so $R_k(C_3) = R_k(K_3)$.
@[category test, AMS 5]
theorem multicolourGraphRamsey_cycleGraph_three (k : ℕ) :
multicolourGraphRamsey k (cycleGraph 3) = multicolourGraphRamsey k (completeGraph (Fin 3)) :=
congrArg (multicolourGraphRamsey k) cycleGraph_three_eq_topWith one colour the only colouring of $K_m$ is $K_m$ itself, and $K_m$ contains $C_5$ exactly when $m \geq 5$.
@[category test, AMS 5]
theorem multicolourGraphRamsey_one_cycleGraph_five :
multicolourGraphRamsey 1 (cycleGraph 5) = 5 := ⊢ multicolourGraphRamsey 1 (cycleGraph 5) = 5
All goals completed! 🐙Let $R_k(G)$ 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_k(C_{2n+1})}{R_k(K_3)}=0$$ for any $n\geq 2$.
A problem of Erdős and Graham. The case $n = 1$ is excluded since $C_3 = K_3$. This problem is #23 in Ramsey Theory in the graphs problem collection.
@[category research open, AMS 5]
theorem erdos_554 (n : ℕ) (hn : 2 ≤ n) :
Tendsto (fun k : ℕ ↦ (multicolourGraphRamsey k (cycleGraph (2 * n + 1)) : ℝ) /
(multicolourGraphRamsey k (completeGraph (Fin 3)) : ℝ)) atTop (𝓝 0) := n:ℕhn:2 ≤ n⊢ Tendsto
(fun k ↦ ↑(multicolourGraphRamsey k (cycleGraph (2 * n + 1))) / ↑(multicolourGraphRamsey k (completeGraph (Fin 3))))
atTop (𝓝 0)
All goals completed! 🐙The problem is open even for $n = 2$: $$\lim_{k\to \infty}\frac{R_k(C_5)}{R_k(K_3)}=0.$$
@[category research open, AMS 5]
theorem erdos_554.variants.n_eq_two :
Tendsto (fun k : ℕ ↦ (multicolourGraphRamsey k (cycleGraph 5) : ℝ) /
(multicolourGraphRamsey k (completeGraph (Fin 3)) : ℝ)) atTop (𝓝 0) := ⊢ Tendsto (fun k ↦ ↑(multicolourGraphRamsey k (cycleGraph 5)) / ↑(multicolourGraphRamsey k (completeGraph (Fin 3)))) atTop
(𝓝 0)
All goals completed! 🐙Bondy and Erdős [BoEr73] and Erdős and Graham [ErGr75] proved the lower bound $$n2^k+1\leq R_k(C_{2n+1})$$ for all $n, k \geq 1$. The condition $k \geq 1$ excludes the junk value $R_0(G) = 2$.
@[category research solved, AMS 5]
theorem erdos_554.variants.lower_bound :
∀ n : ℕ, 1 ≤ n → ∀ k : ℕ, 1 ≤ k →
n * 2 ^ k + 1 ≤ multicolourGraphRamsey k (cycleGraph (2 * n + 1)) := ⊢ ∀ (n : ℕ), 1 ≤ n → ∀ (k : ℕ), 1 ≤ k → n * 2 ^ k + 1 ≤ multicolourGraphRamsey k (cycleGraph (2 * n + 1))
All goals completed! 🐙Erdős and Graham [ErGr75] (see also [BoEr73]) proved the upper bound $$R_k(C_{2n+1})\leq 2n(k+2)!$$ for all $n, k \geq 1$.
@[category research solved, AMS 5]
theorem erdos_554.variants.upper_bound :
∀ n : ℕ, 1 ≤ n → ∀ k : ℕ, 1 ≤ k →
multicolourGraphRamsey k (cycleGraph (2 * n + 1)) ≤ 2 * n * (k + 2).factorial := ⊢ ∀ (n : ℕ), 1 ≤ n → ∀ (k : ℕ), 1 ≤ k → multicolourGraphRamsey k (cycleGraph (2 * n + 1)) ≤ 2 * n * (k + 2).factorial
All goals completed! 🐙
Axenovich, Cames van Batenburg, Janzer, Michel and Rundström [ACJMR26, Theorem 1.1] proved that
$$R_k(C_{2n+1}) \leq (4n-2)^k k^{k/n}+1$$
for all $n, k \geq 1$. For $n \geq 2$ this improves the upper bound in
Erdos554.erdos_554.variants.upper_bound, since $k^{k/n}$ grows much more slowly than $(k+2)!$.
@[category research solved, AMS 5]
theorem erdos_554.variants.acjmr :
∀ n : ℕ, 1 ≤ n → ∀ k : ℕ, 1 ≤ k →
(multicolourGraphRamsey k (cycleGraph (2 * n + 1)) : ℝ) ≤
(4 * n - 2 : ℝ) ^ k * (k : ℝ) ^ ((k : ℝ) / n) + 1 := ⊢ ∀ (n : ℕ),
1 ≤ n →
∀ (k : ℕ), 1 ≤ k → ↑(multicolourGraphRamsey k (cycleGraph (2 * n + 1))) ≤ (4 * ↑n - 2) ^ k * ↑k ^ (↑k / ↑n) + 1
All goals completed! 🐙
Day and Johnson [DaJo17] proved that for every $n \geq 1$ there is a constant $c_n > 0$ such that
$$R_k(C_{2n+1}) > 2n(2+c_n)^{k-1}$$
for all sufficiently large $k$. So the lower bound in Erdos554.erdos_554.variants.lower_bound
is not sharp for fixed $n$ and large $k$.
@[category research solved, AMS 5]
theorem erdos_554.variants.day_johnson :
∀ n : ℕ, 1 ≤ n → ∃ c > (0 : ℝ), ∀ᶠ k : ℕ in atTop,
(2 * n : ℝ) * (2 + c) ^ (k - 1) <
(multicolourGraphRamsey k (cycleGraph (2 * n + 1)) : ℝ) := ⊢ ∀ (n : ℕ),
1 ≤ n →
∃ c > 0, ∀ᶠ (k : ℕ) in atTop, 2 * ↑n * (2 + c) ^ (k - 1) < ↑(multicolourGraphRamsey k (cycleGraph (2 * n + 1)))
All goals completed! 🐙
Jenssen and Skokan [JeSk21] proved that the lower bound in
Erdos554.erdos_554.variants.lower_bound is sharp for fixed $k$ and large $n$: for every
$k \geq 2$,
$$R_k(C_{2n+1}) = n2^k+1$$
for all sufficiently large $n$.
@[category research solved, AMS 5]
theorem erdos_554.variants.jenssen_skokan :
∀ k : ℕ, 2 ≤ k → ∀ᶠ n : ℕ in atTop,
multicolourGraphRamsey k (cycleGraph (2 * n + 1)) = n * 2 ^ k + 1 := ⊢ ∀ (k : ℕ), 2 ≤ k → ∀ᶠ (n : ℕ) in atTop, multicolourGraphRamsey k (cycleGraph (2 * n + 1)) = n * 2 ^ k + 1
All goals completed! 🐙end Erdos554