Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.4 (Erdős) — R(n, n) ≥ n/(e√2) · 2^{n/2}

Proved
AppliedComb.Ramsey.erdos_lower_bound

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1probabilityramsey-theory

Let R(n,n)R(n, n)R(n,n) be the diagonal Ramsey number: the least positive integer NNN such that every finite simple graph with at least NNN vertices contains a complete subgraph on nnn vertices or an independent set of size nnn (Theorem 11.2). Then for every positive integer nnn,

R(n,n)  ≥  ne2 212n.R(n, n) \;\ge\; \frac{n}{e\sqrt{2}}\, 2^{\frac{1}{2} n}.R(n,n)≥e2​n​221​n.

Equivalently, for every integer NNN with 1≤N<ne22n/21 \le N < \frac{n}{e\sqrt2}2^{n/2}1≤N<e2​n​2n/2 there is a simple graph on NNN vertices with no complete subgraph on nnn vertices and no independent set of size nnn. Together with the upper bound R(n,n)≤(2n−2n−1)R(n, n) \le \binom{2n-2}{n-1}R(n,n)≤(n−12n−2​) from the proof of Theorem 11.2, it pins R(n,n)1/nR(n,n)^{1/n}R(n,n)1/n between 2\sqrt 22​ and 444 asymptotically. The result, due to Erdős (1947), is the classical first application of the probabilistic method.

Formalization Note. The bound is stated for every n≥1n \ge 1n≥1, with no asymptotic slack: the book's proof uses Stirling's approximation for n!n!n!, and an explicit lower bound n!≥2πn (n/e)nn! \ge \sqrt{2\pi n}\,(n/e)^nn!≥2πn​(n/e)n suffices for every nnn. The comparison is in R\mathbb RR, with 2n/22^{n/2}2n/2 a real power; R(n,n)R(n,n)R(n,n) is ramseyNumber n n from the definition AppliedComb.Ramsey.ramseyNumber. Because the right-hand side is positive, the statement cannot hold through the junk value sInf ∅ = 0.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_Ramsey_ramseyNumber
Formal statement
namespace AppliedComb.Ramsey

/-- Theorem 11.4 (Erdős), Keller & Trotter p. 232: for every positive integer `n`,
`R(n, n) ≥ n / (e √2) · 2^{n/2}`, where `R(n, n) = ramseyNumber n n` is the least positive
integer such that every graph with at least that many vertices has an `n`-clique or an
independent set of size `n` (Theorem 11.2). -/
theorem erdos_lower_bound (n : ℕ) (hn : 0 < n) :
    (n : ℝ) / (Real.exp 1 * Real.sqrt 2) * (2 : ℝ) ^ ((n : ℝ) / 2) ≤
      (ramseyNumber n n : ℝ) := by sorry

end AppliedComb.Ramsey
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 232, Theorem 11.4
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For every natural number nnn with n≥1n \ge 1n≥1, the statement asserts the real-number inequality

ne 2⋅2 n/2  ≤  R(n,n).\frac{n}{e\,\sqrt{2}} \cdot 2^{\,n/2} \;\le\; R(n,n).e2​n​⋅2n/2≤R(n,n).

The symbols are as follows:

  • e=exp⁡(1)e = \exp(1)e=exp(1) is Euler's number.
  • 2\sqrt{2}2​ is the real square root of 222.
  • 2n/22^{n/2}2n/2 is a real power: the base is 222 and the exponent is the real number n/2n/2n/2, obtained by dividing nnn as a real, not by integer division. So for odd nnn the exponent is a half-integer, and 2n/2=(2) n2^{n/2} = (\sqrt{2})^{\,n}2n/2=(2​)n for every nnn.
  • The left-hand side is evaluated in the real numbers, and the inequality is non-strict (≤\le≤).
  • R(n,n)R(n,n)R(n,n) is the natural number returned by the function ramseyNumber, applied to the pair (n,n)(n, n)(n,n) and then read as a real number. This function comes from the imported module Definitions.Def_AppliedComb_Ramsey_ramseyNumber, and its definition does not appear in the code under audit. So this read-back cannot say what it computes.
  • The declaration's doc-comment says R(n,n)R(n,n)R(n,n) is "the least positive integer such that every graph with at least that many vertices has an nnn-clique or an independent set of size nnn". That is a comment, not part of the formal statement. The theorem is only as meaningful as the actual imported definition, which has to be checked separately.

The statement has one explicit variable, n∈Nn \in \mathbb{N}n∈N, and one hypothesis, 0<n0 < n0<n. There are no other hypotheses, implicit arguments or typeclass assumptions.

The right-hand side is a natural number. So the claim is the same as saying R(n,n)≥⌈ne2 2n/2⌉R(n,n) \ge \left\lceil \frac{n}{e\sqrt{2}}\, 2^{n/2} \right\rceilR(n,n)≥⌈e2​n​2n/2⌉ as natural numbers.

Degenerate cases.

  • n=0n = 0n=0: excluded by the hypothesis, so the statement says nothing about R(0,0)R(0,0)R(0,0).
  • Left side always positive: for every n≥1n \ge 1n≥1 the left-hand side is strictly positive. So the statement always implies R(n,n)≥1R(n,n) \ge 1R(n,n)≥1. In particular, if ramseyNumber returns a default value of 000 for some n≥1n \ge 1n≥1 (for example the infimum of an empty set of natural numbers), the statement would be false for that nnn.
  • n=1n = 1n=1: the left-hand side is 1e2⋅2=1e≈0.368\frac{1}{e\sqrt{2}} \cdot \sqrt{2} = \frac{1}{e} \approx 0.368e2​1​⋅2​=e1​≈0.368. The claim is therefore just R(1,1)≥1R(1,1) \ge 1R(1,1)≥1.
  • n=2n = 2n=2: the left-hand side is 2e2⋅2=22e≈1.04\frac{2}{e\sqrt{2}} \cdot 2 = \frac{2\sqrt{2}}{e} \approx 1.04e2​2​⋅2=e22​​≈1.04. The claim is therefore R(2,2)≥2R(2,2) \ge 2R(2,2)≥2.

The formula has no division by zero (e2>0e\sqrt{2} > 0e2​>0), no subtraction in N\mathbb{N}N, and no real power with a non-positive base. So apart from whatever ramseyNumber itself does in edge cases, no other operation in the statement falls back on a default value.

Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me