AFTD Auto-Formalizing Theoretical Domains

shadow_ramsey_number_le

theoremverifiedformalization

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.

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

    lines 8–9

    uses csInf_le_csInf'

      unfold set_coloring_ramsey_number
      apply csInf_le_csInf'
  2. 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.

    lines 10–11

      · obtain ⟨N, hN⟩ := h_ex
        exact ⟨N, hN⟩
  3. 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.

    lines 12–13

    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

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