AFTD Auto-Formalizing Theoretical Domains

shadow_ramsey_property

theoremverified

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.

  1. 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.

    lines 8–12

    uses Finset.mem_powersetCard

      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
  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.

    lines 13–19

    uses Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, true_and, Finset.card_powersetCard

      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]
  3. 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|.

    lines 20–25

    uses Finset.card_powersetCard, Finset.card_fin

      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
  4. 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'.

    line 26

    uses witness_family_ramsey_property

      exact 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

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'
See it in the graphDiscuss this resultChallenge it