set_coloring_ramsey_property_mono_N
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.
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.
uses
Fin.castLEEmb,SimpleGraph.Embedding.completeGraphclassical 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φ _
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.
obtain ⟨T, hTcard, hcopy⟩ := h φN hφN refine ⟨T, hTcard, ?_⟩
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.
uses
SimpleGraph.comap_adj,SimpleGraph.fromEdgeSet_adj,Set.mem_ofPred_eq,SimpleGraph.Embedding.completeGraph,Subtype.ext,SimpleGraph.Embedding.mapEdgeSet,SimpleGraph.Hom.mapEdgeSet,Sym2.map_mkhave 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)
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.
uses
SimpleGraph.Embedding.comap,SimpleGraph.Copy.ofLErcases 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)⟩