AFTD Auto-Formalizing Theoretical Domains

witness_family_ramsey_number_le

theoremverifiedformalization

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.

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

    lines 11–12

    uses csInf_le_csInf'

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

    lines 13–14

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

    lines 15–16

    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

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