set_coloring_ramsey_number_mono_t
For any simple graph G on a type V and natural numbers r, s, t, if there exists N such that set_coloring_ramsey_property G r s (t + 1) N holds, then set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1).
Statement
open scoped Classical in theorem set_coloring_ramsey_number_mono_t {V : Type*} (G : SimpleGraph V) (r s t : ℕ) (h_ex : ∃ N, set_coloring_ramsey_property G r s (t + 1) N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1)
- Formalizes
- arXiv:2611.15376 Section 7, Eq (37)
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- set_coloring_ramsey_numberGiven a type V, a simple graph G on V, and natural numbers r, s, t, set_coloring_ramsey_number G r s t is the infimum in ℕ of the set of…
- set_coloring_ramsey_property_of_succFor any simple graph G on a type V and natural numbers r, s, t, N, if set_coloring_ramsey_property G r s (t + 1) N holds, then…
- set_coloring_ramsey_propertyGiven a type V, a simple graph G on V, and natural numbers r, s, t, N, set_coloring_ramsey_property G r s t N asserts that for every…
Read back from the Lean
For any type $V$, any simple graph $G$ on $V$, and any natural numbers $r$, $s$, and $t$:
if there exists a natural number $N$ satisfying set_coloring_ramsey_property G r s (t + 1) N,
then set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The generalized set-coloring Ramsey number for parameters (r, s, t) is defined as the infimum of the set of graph orders N satisfying the corresponding Ramsey property. By assumption, the set of such orders for t + 1 is nonempty, so its infimum—the Ramsey number for t + 1—is attained and satisfies the property for t + 1. Because satisfying the Ramsey property for t + 1 implies satisfying it for t, this number also belongs to the set for t, and hence cannot be smaller than the infimum for t.
The set-coloring Ramsey number for parameter t + 1 achieves the Ramsey property for t + 1.
The assumption h_ex provides an order N satisfying the Ramsey property for t + 1, so the set of such orders is nonempty (h_ne). Since every nonempty set of natural numbers contains its infimum (by Nat.sInf_mem), the infimum of this set—which is the Ramsey number for parameter t + 1—itself satisfies the Ramsey property for t + 1.
uses
Nat.sInf_memhave h_ne : {N : ℕ | set_coloring_ramsey_property G r s (t + 1) N}.Nonempty := h_ex have h_mem := Nat.sInf_mem h_ne
The Ramsey number for parameter t + 1 also satisfies the Ramsey property for parameter t.
By set_coloring_ramsey_property_of_succ, any order N that satisfies the set-coloring Ramsey property for parameter t + 1 also satisfies the property for parameter t. Therefore, the Ramsey number for t + 1 belongs to the set of orders satisfying the property for t.
uses
set_coloring_ramsey_property_of_succhave h_sub : set_coloring_ramsey_number G r s (t + 1) ∈ {N : ℕ | set_coloring_ramsey_property G r s t N} := set_coloring_ramsey_property_of_succ G r s t _ h_memset_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1)
By definition, the Ramsey number for parameter t is the infimum of the set of orders satisfying the property for t. Since the Ramsey number for t + 1 belongs to this set, Nat.sInf_le implies that the infimum is less than or equal to it.
uses
Nat.sInf_leexact Nat.sInf_le h_sub
Nat.sInf_mem- Every nonempty set of natural numbers contains its infimum (that is, its minimum element).
set_coloring_ramsey_property_of_succ- If the generalized set-coloring Ramsey property holds for parameter t + 1 on a graph of order N, then it also holds for parameter t on the same order N.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element belonging to the set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Classical in/-- Weak monotonicity of the generalized set-coloring Ramsey number in the intersection parameter t (the intersection spectrum inequality). -/theorem set_coloring_ramsey_number_mono_t {V : Type*} (G : SimpleGraph V) (r s t : ℕ) (h_ex : ∃ N, set_coloring_ramsey_property G r s (t + 1) N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1) := by have h_ne : {N : ℕ | set_coloring_ramsey_property G r s (t + 1) N}.Nonempty := h_ex have h_mem := Nat.sInf_mem h_ne have h_sub : set_coloring_ramsey_number G r s (t + 1) ∈ {N : ℕ | set_coloring_ramsey_property G r s t N} := set_coloring_ramsey_property_of_succ G r s t _ h_mem exact Nat.sInf_le h_sub