shadow_ramsey_number_le
For every 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.choose t) (s.choose t) 1 N holds, then the generalized set-coloring Ramsey number satisfies set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G (r.choose t) (s.choose t) 1.
Statement
open scoped Classical in theorem shadow_ramsey_number_le {V : Type*} (G : SimpleGraph V) (r s t : ℕ) (h_ex : ∃ N, set_coloring_ramsey_property G (r.choose t) (s.choose t) 1 N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G (r.choose t) (s.choose t) 1
- Formalizes
- arXiv:2611.15376 Proposition 3.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_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…
- shadow_ramsey_propertyFor every simple graph G on a type V and natural numbers r, s, t, N, if the set-coloring Ramsey property set_coloring_ramsey_property G…
- witness_family_ramsey_number_leFor every simple graph G on a type V, natural numbers r, s, t, b, and family W of subsets of Fin r such that every member of W has…
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 such that the set-coloring Ramsey property holds for G with parameters (r.choose t, s.choose t, 1, N), then the set-coloring Ramsey number for G with parameters (r, s, t) is less than or equal to the set-coloring Ramsey number for G with parameters (r.choose t, s.choose 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 is defined as the infimum of the integers N satisfying the corresponding Ramsey property. To prove the inequality, it suffices by order properties of infima (csInf_le_csInf') to show that the set of parameters for (r.choose t, s.choose t, 1) is nonempty and contained in the set for (r, s, t). Nonemptiness is given by the assumption, while the inclusion follows directly from the shadow Ramsey property.
The inequality between Ramsey numbers reduces to showing that the set of integers satisfying the Ramsey property for parameters (r.choose t, s.choose t, 1) is nonempty and a subset of the corresponding set for (r, s, t).
Unfolding the definition of set_coloring_ramsey_number expresses each side as the infimum (sInf) of the set of integers N satisfying the respective Ramsey property. Applying csInf_le_csInf' reduces the inequality sInf s ≤ sInf t to checking that t is nonempty and t ⊆ s.
uses
csInf_le_csInf'unfold set_coloring_ramsey_number apply csInf_le_csInf'
The set of integers satisfying the Ramsey property for (r.choose t, s.choose t, 1) is nonempty.
The hypothesis h_ex provides an integer N that satisfies this property, which gives the required witness of nonemptiness.
· obtain ⟨N, hN⟩ := h_ex exact ⟨N, hN⟩
Every integer N satisfying the property for (r.choose t, s.choose t, 1) also satisfies the property for (r, s, t).
Given an arbitrary N with the property for (r.choose t, s.choose t, 1), the lemma shadow_ramsey_property shows that N satisfies the property for (r, s, t), establishing the inclusion of the two sets.
uses
shadow_ramsey_property· intro N hN exact shadow_ramsey_property G r s t N hN
csInf_le_csInf'- In a conditionally complete linear order with a bottom element (such as ℕ), if a subset t is nonempty and t ⊆ s, then sInf s ≤ sInf t.
shadow_ramsey_property- If N satisfies the set-coloring Ramsey property for parameters (r.choose t, s.choose t, 1), then it also satisfies the property for parameters (r, s, t).
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/-- The shadow inequality for generalized set-coloring Ramsey numbers. -/theorem shadow_ramsey_number_le {V : Type*} (G : SimpleGraph V) (r s t : ℕ) (h_ex : ∃ N, set_coloring_ramsey_property G (r.choose t) (s.choose t) 1 N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G (r.choose t) (s.choose t) 1 := by unfold set_coloring_ramsey_number apply csInf_le_csInf' · obtain ⟨N, hN⟩ := h_ex exact ⟨N, hN⟩ · intro N hN exact shadow_ramsey_property G r s t N hN