op_1628_p3_consecutive_equality
The set-coloring Ramsey numbers for the path graph pathGraph 3 with palette parameters r = 4 and s = 3 satisfy set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 1 = set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 2.
Statement
theorem op_1628_p3_consecutive_equality :
set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 1 =
set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 2- Source
- arXiv:2611.15376 Question 7.1
- Verified
- 14 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…
- support_graphGiven a type V, a natural number r, an edge-labeling function ϕ : (⊤ : SimpleGraph V).edgeSet → Finset (Fin r) assigning a finite subset…
- 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…
Read back from the Lean
The set-coloring Ramsey number of the 3-vertex path graph with parameters $r = 4$ colors, edge-set size $s = 3$, and target monochromatic set size $t = 1$ is equal to the set-coloring Ramsey number of the 3-vertex path graph with parameters $r = 4$, $s = 3$, and $t = 2$.
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 proof establishes the equality R(P₃; 4, 3, 1) = R(P₃; 4, 3, 2) by proving that both Ramsey numbers equal 3. For any t ≤ 2, assigning 3 of the 4 colors to each edge of K₃ forces the two edges of P₃ to share at least 3 + 3 - 4 = 2 colors by inclusion-exclusion, so any t of these shared colors form a monochromatic P₃ in K₃. Conversely, P₃ has 3 vertices, so it cannot be embedded into any graph with at most 2 vertices, ruling out N ≤ 2. Thus the minimum host graph order is 3 for both t = 1 and t = 2.
The edges of the path graph P₃ on vertices {0, 1, 2} are precisely e₁ = {0, 1} and e₂ = {1, 2}.
By the definition of the path graph (SimpleGraph.pathGraph_adj), two vertices u, v ∈ Fin 3 are adjacent if and only if their values differ by 1. An exhaustive case check across all pairs of vertices in Fin 3 confirms that the only edges are {0, 1} and {1, 2}, which we name e₁ and e₂ in the complete graph K₃.
uses
SimpleGraph.pathGraph_adjclassical have hall : ∀ u v : Fin 3, (SimpleGraph.pathGraph 3).Adj u v → s(u,v) = s(0,1) ∨ s(u,v) = s(1,2) := by intro u v huv rw [SimpleGraph.pathGraph_adj] at huv fin_cases u <;> fin_cases v <;> simp_all set e1 : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet := ⟨s(0,1), by simp⟩ with he1 set e2 : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet := ⟨s(1,2), by simp⟩ with he2
In any coloring of the edges of K₃ assigning 3 out of 4 colors to each edge, the edges e₁ and e₂ share at least 2 colors.
Each edge receives 3 colors, so |ϕ(e₁)| = 3 and |ϕ(e₂)| = 3. Since the union ϕ(e₁) ∪ ϕ(e₂) is contained in the 4-element palette Fin 4, its cardinality is at most 4 (Finset.card_le_univ). By inclusion-exclusion (Finset.card_union_add_card_inter), |ϕ(e₁) ∪ ϕ(e₂)| + |ϕ(e₁) ∩ ϕ(e₂)| = 3 + 3 = 6, which forces |ϕ(e₁) ∩ ϕ(e₂)| ≥ 6 - 4 = 2.
uses
Finset.card_le_univ,Finset.card_union_add_card_interhave hcard : 2 ≤ (ϕ e1 ∩ ϕ e2).card := by have h1 : (ϕ e1).card = 3 := hϕ e1 have h2 : (ϕ e2).card = 3 := hϕ e2 have hu : (ϕ e1 ∪ ϕ e2).card ≤ 4 := by have := Finset.card_le_univ (ϕ e1 ∪ ϕ e2) simpa using this have := Finset.card_union_add_card_inter (ϕ e1) (ϕ e2) omega
There exists a set of colors T of size t contained in both ϕ(e₁) and ϕ(e₂).
Because t ≤ 2 and |ϕ(e₁) ∩ ϕ(e₂)| ≥ 2, we have t ≤ |ϕ(e₁) ∩ ϕ(e₂)|. Thus the intersection contains a subset T of size t (Finset.exists_subset_card_eq). By definition of intersection (Finset.mem_inter.mp), T is a subset of both ϕ(e₁) and ϕ(e₂).
uses
Finset.exists_subset_card_eq,Finset.mem_inter.mpobtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq (s := ϕ e1 ∩ ϕ e2) (n := t) (by omega) have hT1 : T ⊆ ϕ e1 := fun x hx => (Finset.mem_inter.mp (hTsub hx)).1 have hT2 : T ⊆ ϕ e2 := fun x hx => (Finset.mem_inter.mp (hTsub hx)).2
The path graph P₃ is contained as a subgraph in the support graph of T.
We embed P₃ into the support graph using the identity map on vertices, which is injective. An edge is present in the support graph if T is a subset of its assigned color set (SimpleGraph.fromEdgeSet_adj). Every edge of P₃ is either e₁ or e₂, and T ⊆ ϕ(e₁) as well as T ⊆ ϕ(e₂), so every edge of P₃ is preserved (Subtype.ext, SimpleGraph.Hom.ofLE).
uses
SimpleGraph.Hom.ofLE,SimpleGraph.fromEdgeSet_adj,Subtype.extrefine ⟨T, hTcard, ?_⟩ refine ⟨⟨SimpleGraph.Hom.ofLE ?_, fun a b hab => hab⟩⟩ intro u v huv simp only [support_graph, SimpleGraph.fromEdgeSet_adj] have hmem : s(u,v) ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet := by simpa using huv.ne refine ⟨⟨hmem, ?_⟩, huv.ne⟩ rcases hall u v huv with h | h · have he : (⟨s(u,v), hmem⟩ : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet) = e1 := Subtype.ext h rw [he]; exact hT1 · have he : (⟨s(u,v), hmem⟩ : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet) = e2 := Subtype.ext h rw [he]; exact hT2
The set-coloring Ramsey property holds on 3 vertices for P₃ with parameters r = 4, s = 3, and any t ≤ 2.
Given any edge coloring ϕ assigning 3 colors to each edge of K₃, applying the cherry lemma (op_1628_p3_consecutive_equality_cherry) directly produces a color set T of size t whose support graph contains P₃.
uses
op_1628_p3_consecutive_equality_cherryintro ϕ hϕ exact op_1628_p3_consecutive_equality_cherry ϕ hϕ t ht
The set-coloring Ramsey property fails on any graph with at most 2 vertices.
Suppose for contradiction that the property holds for some N ≤ 2. Testing against the constant coloring where every edge is assigned the color set {0, 1, 2}, there must exist a copy of P₃ in the host graph on N vertices. The vertex map of this copy is an injection from Fin 3 to Fin N, implying 3 ≤ N (Fintype.card_le_of_injective). This contradicts N ≤ 2.
uses
Fintype.card_le_of_injectiveclassical intro hprop obtain ⟨T, -, ⟨copy⟩⟩ := hprop (fun _ => ({0,1,2} : Finset (Fin 4))) (fun e => by simp) have hinj : Function.Injective (fun i : Fin 3 => copy.toHom.toFun i) := copy.injective' have hc := Fintype.card_le_of_injective _ hinj simp at hc omega
For any t ≤ 2, the set-coloring Ramsey number R(P₃; 4, 3, t) equals 3.
The Ramsey number is the infimum of the set of integers N satisfying the property. Since N = 3 satisfies the property (op_1628_p3_consecutive_equality_prop_three), the infimum is at most 3 (Nat.sInf_le). Since the infimum belongs to the set (Nat.sInf_mem) and no N ≤ 2 satisfies the property (op_1628_p3_consecutive_equality_not_prop_le_two), the infimum cannot be ≤ 2, so it is at least 3. By antisymmetry (le_antisymm), the Ramsey number is exactly 3.
uses
op_1628_p3_consecutive_equality_prop_three,le_antisymm,Nat.sInf_le,Nat.sInf_mem,op_1628_p3_consecutive_equality_not_prop_le_twoshow sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} = 3 have h3 : (3:ℕ) ∈ {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} := op_1628_p3_consecutive_equality_prop_three t ht refine le_antisymm (Nat.sInf_le h3) ?_ have hmem : sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} ∈ {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} := Nat.sInf_mem ⟨3, h3⟩ have hnot : ¬ (sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} ≤ 2) := fun h => op_1628_p3_consecutive_equality_not_prop_le_two t _ h hmem omega
The consecutive set-coloring Ramsey numbers coincide: R(P₃; 4, 3, 1) = R(P₃; 4, 3, 2).
Since 1 ≤ 2 and 2 ≤ 2, the previous lemma (op_1628_p3_consecutive_equality_number_eq_three) shows that both R(P₃; 4, 3, 1) = 3 and R(P₃; 4, 3, 2) = 3. Substituting these values into both sides shows they are equal.
uses
op_1628_p3_consecutive_equality_number_eq_threerw [op_1628_p3_consecutive_equality_number_eq_three 1 (by norm_num), op_1628_p3_consecutive_equality_number_eq_three 2 (by norm_num)]
SimpleGraph.pathGraph_adj- Two vertices u and v in the path graph P_n are adjacent if and only if their indices differ by 1.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the type itself.
Finset.card_union_add_card_inter- For any two finite sets, the size of their union plus the size of their intersection equals the sum of their sizes (inclusion-exclusion for two sets).
Finset.exists_subset_card_eq- If n is at most the cardinality of a finite set s, then s contains a subset of cardinality n.
Finset.mem_inter.mp- If an element belongs to the intersection of two sets, it belongs to both sets.
SimpleGraph.Hom.ofLE- If graph G₁ is a subgraph of G₂ on the same vertex set, the identity map is a graph homomorphism from G₁ to G₂.
SimpleGraph.fromEdgeSet_adj- In a graph induced by an edge set, two distinct vertices are adjacent if and only if the edge connecting them belongs to that edge set.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
op_1628_p3_consecutive_equality_cherry- For any edge coloring of K₃ assigning 3 colors out of 4 to each edge and any t ≤ 2, there is a set of t colors whose support graph contains P₃.
Fintype.card_le_of_injective- An injective map from a finite set α to a finite set β implies |α| ≤ |β|.
op_1628_p3_consecutive_equality_prop_three- The set-coloring Ramsey property for P₃ with parameters r = 4, s = 3, and t ≤ 2 holds on 3 vertices.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- If m belongs to a set of natural numbers, the infimum of the set is at most m.
Nat.sInf_mem- The infimum of any nonempty set of natural numbers belongs to that set.
op_1628_p3_consecutive_equality_not_prop_le_two- The set-coloring Ramsey property for P₃ does not hold on any graph with at most 2 vertices.
op_1628_p3_consecutive_equality_number_eq_three- For any t ≤ 2, the set-coloring Ramsey number of P₃ with palette size 4 and edge-color count 3 is equal to 3.
- The lower bound N ≥ 3 does not require analyzing colorings: P₃ has 3 vertices, so it cannot embed into any graph with N ≤ 2 vertices regardless of colors.
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 inprivate lemma op_1628_p3_consecutive_equality_cherry (ϕ : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet → Finset (Fin 4)) (hϕ : ∀ e, (ϕ e).card = 3) (t : ℕ) (ht : t ≤ 2) : ∃ T : Finset (Fin 4), T.card = t ∧ (SimpleGraph.pathGraph 3).IsContained (support_graph ϕ T) := by classical have hall : ∀ u v : Fin 3, (SimpleGraph.pathGraph 3).Adj u v → s(u,v) = s(0,1) ∨ s(u,v) = s(1,2) := by intro u v huv rw [SimpleGraph.pathGraph_adj] at huv fin_cases u <;> fin_cases v <;> simp_all set e1 : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet := ⟨s(0,1), by simp⟩ with he1 set e2 : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet := ⟨s(1,2), by simp⟩ with he2 have hcard : 2 ≤ (ϕ e1 ∩ ϕ e2).card := by have h1 : (ϕ e1).card = 3 := hϕ e1 have h2 : (ϕ e2).card = 3 := hϕ e2 have hu : (ϕ e1 ∪ ϕ e2).card ≤ 4 := by have := Finset.card_le_univ (ϕ e1 ∪ ϕ e2) simpa using this have := Finset.card_union_add_card_inter (ϕ e1) (ϕ e2) omega obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq (s := ϕ e1 ∩ ϕ e2) (n := t) (by omega) have hT1 : T ⊆ ϕ e1 := fun x hx => (Finset.mem_inter.mp (hTsub hx)).1 have hT2 : T ⊆ ϕ e2 := fun x hx => (Finset.mem_inter.mp (hTsub hx)).2 refine ⟨T, hTcard, ?_⟩ refine ⟨⟨SimpleGraph.Hom.ofLE ?_, fun a b hab => hab⟩⟩ intro u v huv simp only [support_graph, SimpleGraph.fromEdgeSet_adj] have hmem : s(u,v) ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet := by simpa using huv.ne refine ⟨⟨hmem, ?_⟩, huv.ne⟩ rcases hall u v huv with h | h · have he : (⟨s(u,v), hmem⟩ : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet) = e1 := Subtype.ext h rw [he]; exact hT1 · have he : (⟨s(u,v), hmem⟩ : ↑(⊤ : SimpleGraph (Fin 3)).edgeSet) = e2 := Subtype.ext h rw [he]; exact hT2open scoped Classical inprivate lemma op_1628_p3_consecutive_equality_prop_three (t : ℕ) (ht : t ≤ 2) : set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t 3 := by intro ϕ hϕ exact op_1628_p3_consecutive_equality_cherry ϕ hϕ t htopen scoped Classical inprivate lemma op_1628_p3_consecutive_equality_not_prop_le_two (t N : ℕ) (hN : N ≤ 2) : ¬ set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N := by classical intro hprop obtain ⟨T, -, ⟨copy⟩⟩ := hprop (fun _ => ({0,1,2} : Finset (Fin 4))) (fun e => by simp) have hinj : Function.Injective (fun i : Fin 3 => copy.toHom.toFun i) := copy.injective' have hc := Fintype.card_le_of_injective _ hinj simp at hc omegaopen scoped Classical inprivate lemma op_1628_p3_consecutive_equality_number_eq_three (t : ℕ) (ht : t ≤ 2) : set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 t = 3 := by show sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} = 3 have h3 : (3:ℕ) ∈ {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} := op_1628_p3_consecutive_equality_prop_three t ht refine le_antisymm (Nat.sInf_le h3) ?_ have hmem : sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} ∈ {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} := Nat.sInf_mem ⟨3, h3⟩ have hnot : ¬ (sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 4 3 t N} ≤ 2) := fun h => op_1628_p3_consecutive_equality_not_prop_le_two t _ h hmem omega/-- Equality of consecutive Ramsey numbers for the path P_3 at r = 4, s = 3, t = 1 and t = 2. -/theorem op_1628_p3_consecutive_equality : set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 1 = set_coloring_ramsey_number (SimpleGraph.pathGraph 3) 4 3 2 := by rw [op_1628_p3_consecutive_equality_number_eq_three 1 (by norm_num), op_1628_p3_consecutive_equality_number_eq_three 2 (by norm_num)]