/-
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 FormalConjecturesUtilErdős Problem 559
References:
[Be83b] Beck, József, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory (1983), 115-129.
[FrPi87] Friedman, J. and Pippenger, N., Expanding graphs contain all small trees. Combinatorica (1987), 71-76.
[HKL95] Haxell, P. E. and Kohayakawa, Y. and Łuczak, T., The induced size-Ramsey number of cycles. Combin. Probab. Comput. (1995), 217-239.
[RoSz00] Rödl, Vojtěch and Szemerédi, Endre, On size Ramsey numbers of graphs with bounded degree. Combinatorica (2000), 257-262.
[Ti22b] Tikhomirov, K., On bounded degree graphs with large size-Ramsey numbers. arXiv:2210.05818 (2022).
[DrPe22] N. Draganić and K. Petrova, Size-Ramsey numbers of graphs with maximum degree three. arXiv:2207.05048 (2022).
@[expose] public sectionopen Filter Real SimpleGraphnamespace Erdos559open scoped Classical inLet $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.
If $G$ has $n$ vertices and maximum degree $d$ then prove that $$\hat{R}(G)\ll_d n.$$
This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that $\hat{R}(G)\gg n(\log n)^{c}$ for some absolute constant $c>0$.
@[category research solved, question, AMS 5, formal_proof using lean4 at
"https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos559.lean#L1275"]
theorem erdos_559 :
¬ ∀ d : ℕ, ∃ C : ℝ, ∀ (V : Type) [Fintype V] (G : SimpleGraph V),
G.maxDegree ≤ d → (sizeRamsey G G : ℝ) ≤ C * Fintype.card V := ⊢ ¬∀ (d : ℕ),
∃ C,
∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V), G.maxDegree ≤ d → ↑(G.sizeRamsey G) ≤ C * ↑(Fintype.card V)
All goals completed! 🐙open scoped Classical inRödl and Szemerédi [RoSz00] disproved the linear bound already for maximum degree $3$.
@[category research solved, AMS 5, formal_proof using lean4 at
"https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos559.lean#L1275"]
theorem erdos_559.variants.degree_three :
¬ ∃ C : ℝ, ∀ (V : Type) [Fintype V] (G : SimpleGraph V),
G.maxDegree ≤ 3 → (sizeRamsey G G : ℝ) ≤ C * Fintype.card V := ⊢ ¬∃ C, ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V), G.maxDegree ≤ 3 → ↑(G.sizeRamsey G) ≤ C * ↑(Fintype.card V)
All goals completed! 🐙open scoped Classical inRödl and Szemerédi [RoSz00] constructed, for infinitely many $n$, a graph on $n$ vertices with maximum degree $3$ such that $\hat{R}(G)\gg n(\log n)^{c}$ for some absolute constant $c>0$.
@[category research solved, AMS 5]
theorem erdos_559.variants.rodl_szemeredi :
∃ c > (0 : ℝ), ∃ C > 0, ∃ᶠ n : ℕ in atTop, ∃ G : SimpleGraph (Fin n),
G.maxDegree ≤ 3 ∧ C * n * (log n) ^ c ≤ sizeRamsey G G := ⊢ ∃ c > 0, ∃ C > 0, ∃ᶠ (n : ℕ) in atTop, ∃ G, G.maxDegree ≤ 3 ∧ C * ↑n * log ↑n ^ c ≤ ↑(G.sizeRamsey G)
All goals completed! 🐙open scoped Classical inTikhomirov [Ti22b] improved this to $\hat{R}(G)\gg n\exp(c\sqrt{\log n})$.
@[category research solved, AMS 5]
theorem erdos_559.variants.tikhomirov :
∃ c > 0, ∃ C > 0, ∃ᶠ n : ℕ in atTop, ∃ G : SimpleGraph (Fin n),
G.maxDegree ≤ 3 ∧ C * n * exp (c * √(log n)) ≤ sizeRamsey G G := ⊢ ∃ c > 0, ∃ C > 0, ∃ᶠ (n : ℕ) in atTop, ∃ G, G.maxDegree ≤ 3 ∧ C * ↑n * rexp (c * √(log ↑n)) ≤ ↑(G.sizeRamsey G)
All goals completed! 🐙open scoped Classical inFriedman and Pippenger [FrPi87] proved the linear bound when $G$ is a tree.
@[category research solved, AMS 5]
theorem erdos_559.variants.trees (d : ℕ) :
∃ C : ℝ, ∀ (V : Type) [Fintype V] (G : SimpleGraph V),
G.IsTree → G.maxDegree ≤ d → (sizeRamsey G G : ℝ) ≤ C * Fintype.card V := d:ℕ⊢ ∃ C,
∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V),
G.IsTree → G.maxDegree ≤ d → ↑(G.sizeRamsey G) ≤ C * ↑(Fintype.card V)
All goals completed! 🐙open scoped Classical inThe best known upper bound for graphs of maximum degree $3$ is $\hat{R}(G)\leq n^{3/2+o(1)}$, due to Draganić and Petrova [DrPe22].
@[category research solved, AMS 5]
theorem erdos_559.variants.draganic_petrova (ε : ℝ) (hε : 0 < ε) :
∀ᶠ n : ℕ in atTop, ∀ G : SimpleGraph (Fin n),
G.maxDegree ≤ 3 → (sizeRamsey G G : ℝ) ≤ (n : ℝ) ^ (3 / 2 + ε : ℝ) := ε:ℝhε:0 < ε⊢ ∀ᶠ (n : ℕ) in atTop, ∀ (G : SimpleGraph (Fin n)), G.maxDegree ≤ 3 → ↑(G.sizeRamsey G) ≤ ↑n ^ (3 / 2 + ε)
All goals completed! 🐙end Erdos559