AFTD Auto-Formalizing Theoretical Domains

set_coloring_ramsey_property_of_succ

theoremverifiedformalization

For any simple graph G on a type V and natural numbers r, s, t, N, if set_coloring_ramsey_property G r s (t + 1) N holds, then set_coloring_ramsey_property G r s t N holds.

Statement

open scoped Classical in
theorem set_coloring_ramsey_property_of_succ
    {V : Type*} (G : SimpleGraph V) (r s t N : ℕ)
    (h : set_coloring_ramsey_property G r s (t + 1) N) :
    set_coloring_ramsey_property G r s t N
Formalizes
arXiv:2611.15376 Section 7, Eq (37)
Verified
14 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…
  • support_graphGiven a type V, a natural number r, an edge-labeling function ϕ : (⊤ : SimpleGraph V).edgeSet → Finset (Fin r) assigning a finite subset…
Used by 1
  • set_coloring_ramsey_number_mono_tFor any 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 s (t + 1) N…

Read back from the Lean

For any type V, simple graph G on V, and natural numbers r, s, t, and N, if G satisfies set_coloring_ramsey_property G r s (t + 1) N, then G satisfies 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

To show that the set-coloring Ramsey property is monotonic in the intersection parameter t, we start with any edge coloring ϕ and apply the Ramsey hypothesis for t + 1 to obtain a color set T_succ of size t + 1 whose support graph contains a copy of G. Since |T_succ| ≥ 1, deleting an arbitrary color x ∈ T_succ yields a set T of size t. Because T ⊆ T_succ, requiring edges to contain all colors in T is a weaker condition than requiring all colors in T_succ, so the support graph only gains edges and the copy of G remains valid.

  1. Given an edge coloring ϕ, there exists a subset T_succ of t + 1 colors whose support graph contains a copy of G.

    We introduce an arbitrary valid s-coloring ϕ of the edges of the complete graph on N vertices. Applying the hypothesis h (the Ramsey property with parameter t + 1) to ϕ produces a subset T_succ of colors with |T_succ| = t + 1 such that G embeds into the support graph of T_succ.

    lines 7–8

      intro ϕ hϕ
      obtain ⟨T_succ, hT_card, hT_cont⟩ := h ϕ hϕ
  2. It suffices to show that removing an element x ∈ T_succ yields a t-element color set whose support graph contains a copy of G.

    Since |T_succ| = t + 1 ≥ 1, the cardinality of T_succ is strictly positive, so T_succ is nonempty by Finset.card_pos.mp. We choose an element x ∈ T_succ and propose T_succ \ {x} as the candidate t-element subset, splitting the goal into verifying its cardinality and the containment of G.

    lines 9–12

    uses Finset.card_pos.mp

      have hpos : 0 < T_succ.card := by omega
      have hne : T_succ.Nonempty := Finset.card_pos.mp hpos
      obtain ⟨x, hx⟩ := hne
      refine ⟨T_succ.erase x, ?_, ?_⟩
  3. The set T_succ \ {x} has cardinality t.

    Because x ∈ T_succ, erasing x reduces the size of T_succ by 1 by Finset.card_erase_of_mem. Since |T_succ| = t + 1, the new size is (t + 1) - 1, which equals t by Nat.succ_sub_one.

    lines 13–14

    uses Finset.card_erase_of_mem, Nat.succ_sub_one

      · rw [Finset.card_erase_of_mem hx, hT_card]
        exact Nat.succ_sub_one t
  4. The vertex map from the embedding of G into the support graph of T_succ serves as a candidate embedding into the support graph of T_succ \ {x}.

    Unpacking the assumption that G embeds into the support graph of T_succ gives an embedding f. We reuse the same vertex mapping and its injectivity, reducing the containment goal to verifying that f preserves adjacency into the support graph of T_succ \ {x}.

    lines 15–16

      · obtain ⟨f⟩ := hT_cont
        refine ⟨⟨⟨f.toHom, fun hadj => ?_⟩, f.injective'⟩⟩
  5. The support graph of T_succ is a subgraph of the support graph of T_succ \ {x}.

    By the definition of support_graph and SimpleGraph.fromEdgeSet_adj, an edge is present in the support graph of a color set if all colors in that set appear on that edge. Since T_succ \ {x} ⊆ T_succ by Finset.erase_subset, any edge containing all colors of T_succ also contains all colors of T_succ \ {x}.

    lines 17–23

    uses SimpleGraph.fromEdgeSet_adj, Finset.erase_subset

        have hle : support_graph ϕ T_succ ≤ support_graph ϕ (T_succ.erase x) := by
          intro v w hw
          rw [support_graph] at hw ⊢
          rw [SimpleGraph.fromEdgeSet_adj] at hw ⊢
          refine ⟨?_, hw.2⟩
          rcases hw.1 with ⟨hedge, hsub⟩
          exact ⟨hedge, (Finset.erase_subset x T_succ).trans hsub⟩
  6. The map f preserves adjacency, confirming that G is contained in the support graph of T_succ \ {x}.

    Because f is a graph homomorphism into the support graph of T_succ, any edge of G maps to an edge in that graph. By the subgraph inclusion proved in the previous step, that edge is also present in the support graph of T_succ \ {x}, completing the proof.

    line 24

        exact hle (f.toHom.map_rel hadj)
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.card_erase_of_mem
Removing an element from a finite set that contains it decreases the set's cardinality by 1.
Nat.succ_sub_one
For any natural number n, (n + 1) - 1 = n.
SimpleGraph.fromEdgeSet_adj
In a graph constructed from an edge set, two vertices are adjacent if and only if their unordered pair is in the edge set and the two vertices are distinct.
Finset.erase_subset
Removing an element from a finite set yields a subset of the original set.

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/-- Monotonicity of set-coloring Ramsey property in the intersection parameter t: if every coloring has a (t+1)-monochromatic copy, it has a t-monochromatic copy. -/theorem set_coloring_ramsey_property_of_succ    {V : Type*} (G : SimpleGraph V) (r s t N : ℕ)    (h : set_coloring_ramsey_property G r s (t + 1) N) :    set_coloring_ramsey_property G r s t N := by  intro ϕ hϕ  obtain ⟨T_succ, hT_card, hT_cont⟩ := h ϕ hϕ  have hpos : 0 < T_succ.card := by omega  have hne : T_succ.Nonempty := Finset.card_pos.mp hpos  obtain ⟨x, hx⟩ := hne  refine ⟨T_succ.erase x, ?_, ?_⟩  · rw [Finset.card_erase_of_mem hx, hT_card]    exact Nat.succ_sub_one t  · obtain ⟨f⟩ := hT_cont    refine ⟨⟨⟨f.toHom, fun hadj => ?_⟩, f.injective'⟩⟩    have hle : support_graph ϕ T_succ ≤ support_graph ϕ (T_succ.erase x) := by      intro v w hw      rw [support_graph] at hw ⊢      rw [SimpleGraph.fromEdgeSet_adj] at hw ⊢      refine ⟨?_, hw.2⟩      rcases hw.1 with ⟨hedge, hsub⟩      exact ⟨hedge, (Finset.erase_subset x T_succ).trans hsub⟩    exact hle (f.toHom.map_rel hadj)
See it in the graphDiscuss this resultChallenge it