AFTD Auto-Formalizing Theoretical Domains

set_coloring_ramsey_property_mono_N

theoremverified

For any simple graph G, palette size r, edge subset size s, intersection parameter t, and natural numbers N ≤ M, if every (r, s)-set-coloring of K_N contains a t-monochromatic copy of G, then every (r, s)-set-coloring of K_M also contains a t-monochromatic copy of G.

Statement

theorem set_coloring_ramsey_property_mono_N {V : Type*} (G : SimpleGraph V) (r s t : ℕ)
    {N M : ℕ} (hNM : N ≤ M) (h : set_coloring_ramsey_property G r s t N) :
    set_coloring_ramsey_property G r s t M
Source
folklore
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…
  • 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_p3_oneFor all integers a ≥ b ≥ 1, the set-coloring Ramsey number of the two-edge path P_3 with intersection parameter t = 1 is given by R(P_3;…

Read back from the Lean

For any type V, any simple graph G on V, natural numbers r, s, t, and natural numbers N, M such that N ≤ M: if the set-coloring Ramsey property set_coloring_ramsey_property G r s t N holds, then set_coloring_ramsey_property G r s t M also holds. That is, the property that every s-element set-coloring of the edges of the complete graph on N vertices contains a copy of G whose edges all share a common t-subset of colors is monotone non-decreasing in the number of vertices 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 monotone in the number of vertices (N ≤ M), any (r, s)-set-coloring φ of K_M is pulled back along the canonical vertex embedding f : Fin N ↪ Fin M to an (r, s)-set-coloring φ_N of K_N. By the Ramsey hypothesis on K_N, there is a color subset T of size t whose support graph in K_N contains a copy of G. This support graph is shown to be a subgraph of the pullback graph of the support graph of φ at T. Composing the copy of G with this subgraph inclusion and the canonical embedding of the pullback graph into the support graph in K_M produces the required copy of G in K_M.

  1. An (r, s)-set-coloring φ of K_M induces an (r, s)-set-coloring φ_N on K_N via the canonical vertex inclusion.

    Given an (r, s)-set-coloring φ of the complete graph K_M, we use N ≤ M to obtain the canonical vertex embedding f : Fin N ↪ Fin M via Fin.castLEEmb. This induces an embedding of complete graphs K_N ↪ K_M via SimpleGraph.Embedding.completeGraph. Pulling back φ along this embedding yields an edge coloring φ_N on K_N. Since every edge of K_M is assigned an s-element subset of colors, φ_N also assigns an s-element subset to each edge of K_N.

    lines 5–10

    uses Fin.castLEEmb, SimpleGraph.Embedding.completeGraph

      classical
      intro φ hφ
      let f : Fin N ↪ Fin M := Fin.castLEEmb hNM
      let φN : (⊤ : SimpleGraph (Fin N)).edgeSet → Finset (Fin r) :=
        fun e => φ ((SimpleGraph.Embedding.completeGraph f).mapEdgeSet e)
      have hφN : ∀ e, (φN e).card = s := fun e => hφ _
  2. There exists a color subset T of size t such that G embeds into the support graph of φ_N at T, and it suffices to show G embeds into the support graph of φ at T.

    Applying the hypothesis that K_N satisfies the (r, s, t)-Ramsey property for G to the coloring φ_N, we obtain a subset of colors T of size t whose support graph in K_N contains a copy of G. We choose this set T as the witness for K_M, reducing the goal to showing that G is contained in the support graph of φ at T.

    lines 11–12

      obtain ⟨T, hTcard, hcopy⟩ := h φN hφN
      refine ⟨T, hTcard, ?_⟩
  3. The support graph of φ_N at T is a subgraph of the pullback under f of the support graph of φ at T.

    Suppose u and v are adjacent in the support graph of φ_N at T. By SimpleGraph.fromEdgeSet_adj, this means u ≠ v and T ⊆ φ_N(uv). Because f is injective, f(u) ≠ f(v). The edge e_M connecting f(u) and f(v) in K_M is the image of the edge e_N = uv under f, as shown using Subtype.ext, SimpleGraph.Embedding.mapEdgeSet, SimpleGraph.Hom.mapEdgeSet, and Sym2.map_mk. Consequently, φ(e_M) = φ_N(e_N) ⊇ T, so f(u) and f(v) are adjacent in the support graph of φ at T. By SimpleGraph.comap_adj, this is equivalent to u and v being adjacent in the pullback graph along f.

    lines 13–30

    uses SimpleGraph.comap_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq, SimpleGraph.Embedding.completeGraph, Subtype.ext, SimpleGraph.Embedding.mapEdgeSet, SimpleGraph.Hom.mapEdgeSet, Sym2.map_mk

      have hle : support_graph φN T ≤ (support_graph φ T).comap f := by
        intro u v huv
        simp only [SimpleGraph.comap_adj]
        simp only [support_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] at huv ⊢
        rcases huv with ⟨⟨hN, hsub⟩, hne⟩
        let eN : (⊤ : SimpleGraph (Fin N)).edgeSet := ⟨s(u, v), hN⟩
        let eM : (⊤ : SimpleGraph (Fin M)).edgeSet :=
          (SimpleGraph.Embedding.completeGraph f).mapEdgeSet eN
        have heq : eM = ⟨s(f u, f v), eM.property⟩ := by
          apply Subtype.ext
          dsimp [eM, eN]
          simp [SimpleGraph.Embedding.mapEdgeSet, SimpleGraph.Hom.mapEdgeSet, Sym2.map_mk]
        refine ⟨⟨eM.property, ?_⟩, ?_⟩
        · show T ⊆ φ ⟨s(f u, f v), eM.property⟩
          rw [← heq]
          exact hsub
        · intro h
          exact hne (f.injective h)
  4. The copy of G in the support graph of φ_N embeds into the support graph of φ at T.

    By SimpleGraph.Copy.ofLE, the subgraph inclusion shows that the copy of G in the support graph of φ_N embeds into the pullback graph along f. Composing this with the canonical embedding from the pullback graph into the support graph of φ at T provided by SimpleGraph.Embedding.comap yields a copy of G in the support graph of φ at T.

    lines 31–33

    uses SimpleGraph.Embedding.comap, SimpleGraph.Copy.ofLE

      rcases hcopy with ⟨c⟩
      exact ⟨(SimpleGraph.Embedding.comap f (support_graph φ T)).toCopy.comp
        ((SimpleGraph.Copy.ofLE (support_graph φN T) ((support_graph φ T).comap f) hle).comp c)⟩
Fin.castLEEmb
Given n ≤ m, the canonical embedding from Fin n into Fin m that preserves values.
SimpleGraph.Embedding.completeGraph
An embedding between vertex types α ↪ β induces a graph embedding between complete graphs on α and β.
SimpleGraph.comap_adj
Two vertices u and v are adjacent in the pullback graph comap f G if and only if their images f(u) and f(v) are adjacent in G.
SimpleGraph.fromEdgeSet_adj
In the simple graph formed from an edge set s, vertices v and w are adjacent if and only if the pair s(v, w) belongs to s and v ≠ w.
Set.mem_ofPred_eq
An element x belongs to the set comprehension {y | p y} if and only if p(x) holds.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
SimpleGraph.Embedding.mapEdgeSet
A graph embedding induces an injective map between the edge sets of the domain and codomain graphs.
SimpleGraph.Hom.mapEdgeSet
A graph homomorphism induces a map from the domain graph's edge set to the codomain graph's edge set.
Sym2.map_mk
The image of an unordered pair s(a, b) under a function f is the unordered pair s(f(a), f(b)).
SimpleGraph.Embedding.comap
For an injective map f on vertices, the pullback graph comap f G canonically embeds into G.
SimpleGraph.Copy.ofLE
If G₁ is a subgraph of G₂ on the same vertex type (G₁ ≤ G₂), then G₁ embeds into G₂ via the identity map.

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

/-- Monotonicity of the set-coloring Ramsey property in the number of vertices. -/theorem set_coloring_ramsey_property_mono_N {V : Type*} (G : SimpleGraph V) (r s t : ℕ)    {N M : ℕ} (hNM : N ≤ M) (h : set_coloring_ramsey_property G r s t N) :    set_coloring_ramsey_property G r s t M := by  classical  intro φ hφ  let f : Fin N ↪ Fin M := Fin.castLEEmb hNM  let φN : (⊤ : SimpleGraph (Fin N)).edgeSet → Finset (Fin r) :=    fun e => φ ((SimpleGraph.Embedding.completeGraph f).mapEdgeSet e)  have hφN : ∀ e, (φN e).card = s := fun e => hφ _  obtain ⟨T, hTcard, hcopy⟩ := h φN hφN  refine ⟨T, hTcard, ?_⟩  have hle : support_graph φN T ≤ (support_graph φ T).comap f := by    intro u v huv    simp only [SimpleGraph.comap_adj]    simp only [support_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] at huv ⊢    rcases huv with ⟨⟨hN, hsub⟩, hne⟩    let eN : (⊤ : SimpleGraph (Fin N)).edgeSet := ⟨s(u, v), hN⟩    let eM : (⊤ : SimpleGraph (Fin M)).edgeSet :=      (SimpleGraph.Embedding.completeGraph f).mapEdgeSet eN    have heq : eM = ⟨s(f u, f v), eM.property⟩ := by      apply Subtype.ext      dsimp [eM, eN]      simp [SimpleGraph.Embedding.mapEdgeSet, SimpleGraph.Hom.mapEdgeSet, Sym2.map_mk]    refine ⟨⟨eM.property, ?_⟩, ?_⟩    · show T ⊆ φ ⟨s(f u, f v), eM.property⟩      rw [← heq]      exact hsub    · intro h      exact hne (f.injective h)  rcases hcopy with ⟨c⟩  exact ⟨(SimpleGraph.Embedding.comap f (support_graph φ T)).toCopy.comp    ((SimpleGraph.Copy.ofLE (support_graph φN T) ((support_graph φ T).comap f) hle).comp c)⟩
See it in the graphDiscuss this resultChallenge it