Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Graph theory P-erdos-87

Erdős Problem #87

Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-erdos-87,
  title        = {Erdős Problem #87},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-87}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

erdos_87.parts.i. Let . Is it true that, if is sufficiently large, then for every graph with chromatic number ?

The restriction excludes negative bases in .

This problem is #12 in Ramsey Theory in the graphs problem collection.

erdos_87.parts.ii. Even stronger, is there some such that, for all large , for every graph with chromatic number ?

This problem is #13 in Ramsey Theory in the graphs problem collection.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«87» (2 statements). answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem erdos_87.parts.i : answer(sorry) ↔
    ∀ ε > (0 : ℝ), ε < 1 → ∀ᶠ k : ℕ in atTop,
      ∀ (V : Type) [Fintype V] (G : SimpleGraph V), G.chromaticNumber = (k : ℕ∞) →
        (SimpleGraph.diagonalGraphRamsey G : ℝ) >
          (1 - ε) ^ k * (SimpleGraph.diagonalRamsey k : ℝ)
theorem erdos_87.parts.ii : answer(sorry) ↔
    ∃ c > (0 : ℝ), ∀ᶠ k : ℕ in atTop,
      ∀ (V : Type) [Fintype V] (G : SimpleGraph V), G.chromaticNumber = (k : ℕ∞) →
        (SimpleGraph.diagonalGraphRamsey G : ℝ) > c * (SimpleGraph.diagonalRamsey k : ℝ)

What counts as progress

  • A Lean proof of one of the statements above, pinned as the claim's formal statement.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already — check erdosproblems.com/87. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

  • erdosproblems.com/87
  • [Er95] Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.