set_coloring_ramsey_property_of_succ
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.
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.
intro ϕ hϕ obtain ⟨T_succ, hT_card, hT_cont⟩ := h ϕ hϕ
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.
uses
Finset.card_pos.mphave 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, ?_, ?_⟩
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.
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
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}.
· obtain ⟨f⟩ := hT_cont refine ⟨⟨⟨f.toHom, fun hadj => ?_⟩, f.injective'⟩⟩
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}.
uses
SimpleGraph.fromEdgeSet_adj,Finset.erase_subsethave 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⟩
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.
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
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.
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)