witness_family_ramsey_number_le
For 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 cardinality t and every s-subset of Fin r contains at least b members of W, if there exists N such that set_coloring_ramsey_property G W.card b 1 N holds, then set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G W.card b 1.
Statement
open scoped Classical in theorem witness_family_ramsey_number_le {V : Type*} (G : SimpleGraph V) (r s t b : ℕ) (W : Finset (Finset (Fin r))) (hW_card : ∀ w ∈ W, w.card = t) (hW_cov : ∀ S : Finset (Fin r), S.card = s → b ≤ (W.filter (· ⊆ S)).card) (h_ex : ∃ N, set_coloring_ramsey_property G W.card b 1 N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G W.card b 1
- Formalizes
- arXiv:2611.15376 Proposition 3.1
- Verified
- 15 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_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…
- witness_family_ramsey_propertyFor every simple graph G on a type V, natural numbers r, s, t, b, N, and family W of subsets of Fin r such that every member of W has…
- Used by 1
- shadow_ramsey_number_leFor 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)…
Read back from the Lean
Let $V$ be a type and $G$ a simple graph on $V$. Let $r, s, t, b \in \mathbb{N}$, and let $W$ be a finite set of subsets of $\operatorname{Fin} r$. Assume:
1. Every $w \in W$ has cardinality $t$ (hW_card).
2. For every subset $S \subseteq \operatorname{Fin} r$ of cardinality $s$, there are at least $b$ elements of $W$ that are subsets of $S$ (hW_cov).
3. There exists some $N \in \mathbb{N}$ satisfying the set-coloring Ramsey property for $G$ with parameters $(|W|, b, 1, N)$ (h_ex).
Then the set-coloring Ramsey number of $G$ with parameters $(r, s, t)$ is less than or equal to the set-coloring Ramsey number of $G$ with parameters $(|W|, b, 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 theorem reduces the generalized set-coloring Ramsey number for parameters $(r, s, t)$ to that for parameters $(|W|, b, 1)$. Because the Ramsey number is defined as the infimum over all graph orders $N$ satisfying the Ramsey property, the inequality follows from the monotonicity of the infimum under set inclusion: any order $N$ valid for $(|W|, b, 1)$ is also valid for $(r, s, t)$ by a reduction lemma (`witness_family_ramsey_property`), and the assumption `h_ex` guarantees that at least one such $N$ exists.
To bound the Ramsey number, it suffices to show that the set of sizes $N$ satisfying the Ramsey property for parameters $(|W|, b, 1)$ is non-empty and is a subset of the set of sizes satisfying the property for $(r, s, t)$.
By definition, the set-coloring Ramsey number is the infimum of the set of orders $N$ satisfying the property. Applying `csInf_le_csInf'`, the infimum of a set of natural numbers is at most the infimum of any non-empty subset of it.
uses
csInf_le_csInf'unfold set_coloring_ramsey_number apply csInf_le_csInf'
The set of orders $N$ satisfying the Ramsey property for parameters $(|W|, b, 1)$ is non-empty.
The hypothesis `h_ex` explicitly provides an integer $N$ satisfying `set_coloring_ramsey_property G W.card b 1 N`, which serves as a witness that the set is non-empty.
· obtain ⟨N, hN⟩ := h_ex exact ⟨N, hN⟩
Every order $N$ satisfying the Ramsey property for $(|W|, b, 1)$ also satisfies the property for $(r, s, t)$.
Given an arbitrary $N$ with this property, `witness_family_ramsey_property` deduces that $N$ also satisfies the property for $(r, s, t)$, using the assumptions that every member of $W$ has size $t$ and every $s$-subset contains at least $b$ members of $W$.
uses
witness_family_ramsey_property· intro N hN exact witness_family_ramsey_property G r s t b N W hW_card hW_cov hN
csInf_le_csInf'- In a conditionally complete linear order with a bottom element (such as the natural numbers), if a set $t$ is non-empty and $t \subseteq s$, then $\inf s \le \inf t$.
witness_family_ramsey_property- If $W$ is a family of $t$-element subsets of $\{0, \dots, r-1\}$ such that every $s$-element subset contains at least $b$ members of $W$, then any order $N$ satisfying the Ramsey property for parameters $(|W|, b, 1)$ also satisfies the Ramsey property for $(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/-- Reduction of generalized set-coloring Ramsey numbers via witness families (Proposition 3.1). -/theorem witness_family_ramsey_number_le {V : Type*} (G : SimpleGraph V) (r s t b : ℕ) (W : Finset (Finset (Fin r))) (hW_card : ∀ w ∈ W, w.card = t) (hW_cov : ∀ S : Finset (Fin r), S.card = s → b ≤ (W.filter (· ⊆ S)).card) (h_ex : ∃ N, set_coloring_ramsey_property G W.card b 1 N) : set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G W.card b 1 := by unfold set_coloring_ramsey_number apply csInf_le_csInf' · obtain ⟨N, hN⟩ := h_ex exact ⟨N, hN⟩ · intro N hN exact witness_family_ramsey_property G r s t b N W hW_card hW_cov hN