shadow_ramsey_property
For 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 (r.choose t) (s.choose t) 1 N holds, then set_coloring_ramsey_property G r s t N holds.
Statement
open scoped Classical in theorem shadow_ramsey_property {V : Type*} (G : SimpleGraph V) (r s t N : ℕ) (h_prop : set_coloring_ramsey_property G (r.choose t) (s.choose t) 1 N) : set_coloring_ramsey_property G r s t N
- Source
- arXiv:2611.15376 Proposition 3.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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
For any type $V$, any simple graph $G$ on $V$, and any natural numbers $r, s, t, N$:
if the set-coloring Ramsey property holds for $G$ with parameters $\binom{r}{t}$, $\binom{s}{t}$, $1$, and $N$ (that is, set_coloring_ramsey_property G (r.choose t) (s.choose t) 1 N),
then the set-coloring Ramsey property holds for $G$ with parameters $r, s, t$, and $N$ (that is, set_coloring_ramsey_property G r s t N).
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 proof reduces the set-coloring Ramsey property for parameters (r, s, t, N) to the assumed property for parameters ((r choose t), (s choose t), 1, N) via the transfer theorem witness_family_ramsey_property. The witness family W is chosen to be the collection of all t-element subsets of {0, ..., r-1}. Since every member of W has size t, any s-element subset contains exactly (s choose t) members of W, and |W| = (r choose t), the conditions of the transfer theorem are directly verified.
Define the witness family W as the collection of all t-element subsets of {0, ..., r-1}, and establish that each element of W has cardinality t.
We define W to be the powerset of Fin r restricted to subsets of size t. For any w ∈ W, Finset.mem_powersetCard shows that w is a subset of Finset.univ with card w = t, whose second component yields |w| = t directly.
uses
Finset.mem_powersetCardlet W : Finset (Finset (Fin r)) := (Finset.univ : Finset (Fin r)).powersetCard t have hW_card : ∀ w ∈ W, w.card = t := by intro w hw rw [Finset.mem_powersetCard] at hw exact hw.2
Every subset S ⊆ {0, ..., r-1} of size s contains at least (s choose t) members of W.
Given a set S with |S| = s, the subcollection of sets in W that are contained in S is shown by extensionality to be exactly the family of all t-element subsets of S (Finset.powersetCard t S), since being a subset of S automatically implies being a subset of the universe. By Finset.card_powersetCard, this subcollection has cardinality (|S| choose t) = (s choose t), which trivially satisfies the inequality.
uses
Finset.mem_filter,Finset.mem_powersetCard,Finset.subset_univ,true_and,Finset.card_powersetCardhave hW_cov : ∀ (S : Finset (Fin r)), S.card = s → s.choose t ≤ (W.filter (· ⊆ S)).card := by intro S hS have h_eq : W.filter (· ⊆ S) = S.powersetCard t := by ext x simp only [Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, true_and, W] tauto rw [h_eq, Finset.card_powersetCard, hS]
The family W has cardinality (r choose t), so the hypothesis translates to set_coloring_ramsey_property G W.card (s.choose t) 1 N.
Unfolding the definition of W, its cardinality is the number of t-element subsets of Finset.univ for Fin r. Since |Fin r| = r by Finset.card_fin, Finset.card_powersetCard gives |W| = (r choose t). Rewriting (r choose t) with |W| in the hypothesis h_prop yields the required Ramsey property on palette size |W|.
uses
Finset.card_powersetCard,Finset.card_finhave hW_card_eq : W.card = r.choose t := by dsimp [W] rw [Finset.card_powersetCard, Finset.card_fin] have h_prop' : set_coloring_ramsey_property G W.card (s.choose t) 1 N := by rw [hW_card_eq] exact h_prop
The set-coloring Ramsey property set_coloring_ramsey_property G r s t N holds.
We apply the transfer theorem witness_family_ramsey_property using the witness family W, the uniform element size condition hW_card, the coverage condition hW_cov, and the adapted hypothesis h_prop'.
uses
witness_family_ramsey_propertyexact witness_family_ramsey_property G r s t (s.choose t) N W hW_card hW_cov h_prop'
Finset.mem_powersetCard- A finite set s belongs to the subcollection of n-element subsets of t if and only if s ⊆ t and |s| = n.
Finset.mem_filter- An element a belongs to the filtered subcollection {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds.
Finset.subset_univ- Every finite subset of a finite type is a subset of the universal set.
true_and- The conjunction of True and a proposition p is logically equivalent to p.
Finset.card_powersetCard- The number of n-element subsets of a finite set s is (|s| choose n).
Finset.card_fin- The universal set of Fin n has cardinality n.
witness_family_ramsey_property- If W is a family of t-element subsets of {0, ..., r-1} such that every s-subset contains at least b members of W, then the set-coloring Ramsey property with parameters (|W|, b, 1, N) implies the property with parameters (r, s, t, N).
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/-- Shadow inequality for set-coloring Ramsey property. -/theorem shadow_ramsey_property {V : Type*} (G : SimpleGraph V) (r s t N : ℕ) (h_prop : set_coloring_ramsey_property G (r.choose t) (s.choose t) 1 N) : set_coloring_ramsey_property G r s t N := by let W : Finset (Finset (Fin r)) := (Finset.univ : Finset (Fin r)).powersetCard t have hW_card : ∀ w ∈ W, w.card = t := by intro w hw rw [Finset.mem_powersetCard] at hw exact hw.2 have hW_cov : ∀ (S : Finset (Fin r)), S.card = s → s.choose t ≤ (W.filter (· ⊆ S)).card := by intro S hS have h_eq : W.filter (· ⊆ S) = S.powersetCard t := by ext x simp only [Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, true_and, W] tauto rw [h_eq, Finset.card_powersetCard, hS] have hW_card_eq : W.card = r.choose t := by dsimp [W] rw [Finset.card_powersetCard, Finset.card_fin] have h_prop' : set_coloring_ramsey_property G W.card (s.choose t) 1 N := by rw [hW_card_eq] exact h_prop exact witness_family_ramsey_property G r s t (s.choose t) N W hW_card hW_cov h_prop'