Theorem 11.4 (Erdős) — R(n, n) ≥ n/(e√2) · 2^{n/2}
ProvedAppliedComb.Ramsey.erdos_lower_boundLet be the diagonal Ramsey number: the least positive integer such that every finite simple graph with at least vertices contains a complete subgraph on vertices or an independent set of size (Theorem 11.2). Then for every positive integer ,
Equivalently, for every integer with there is a simple graph on vertices with no complete subgraph on vertices and no independent set of size . Together with the upper bound from the proof of Theorem 11.2, it pins between and 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 , with no asymptotic slack: the book's proof uses Stirling's approximation for , and an explicit lower bound suffices for every . The comparison is in , with a real power; 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.
import Mathlib import Definitions.Def_AppliedComb_Ramsey_ramseyNumber
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every natural number with , the statement asserts the real-number inequality
The symbols are as follows:
- is Euler's number.
- is the real square root of .
- is a real power: the base is and the exponent is the real number , obtained by dividing as a real, not by integer division. So for odd the exponent is a half-integer, and for every .
- The left-hand side is evaluated in the real numbers, and the inequality is non-strict ().
- is the natural number returned by the function
ramseyNumber, applied to the pair and then read as a real number. This function comes from the imported moduleDefinitions.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 is "the least positive integer such that every graph with at least that many vertices has an -clique or an independent set of size ". 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, , and one hypothesis, . 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 as natural numbers.
Degenerate cases.
- : excluded by the hypothesis, so the statement says nothing about .
- Left side always positive: for every the left-hand side is strictly positive. So the statement always implies . In particular, if
ramseyNumberreturns a default value of for some (for example the infimum of an empty set of natural numbers), the statement would be false for that . - : the left-hand side is . The claim is therefore just .
- : the left-hand side is . The claim is therefore .
The formula has no division by zero (), no subtraction in , 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.