AFTD Auto-Formalizing Theoretical Domains

op_1628_p3_consecutive_equality

theoremverified

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.

  1. 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₃.

    lines 7–14

    uses SimpleGraph.pathGraph_adj

      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
  2. 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.

    lines 15–22

    uses Finset.card_le_univ, Finset.card_union_add_card_inter

      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
  3. 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₂).

    lines 23–25

    uses Finset.exists_subset_card_eq, Finset.mem_inter.mp

      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
  4. 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).

    lines 26–37

    uses SimpleGraph.Hom.ofLE, SimpleGraph.fromEdgeSet_adj, Subtype.ext

      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 hT2
  5. 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₃.

    lines 42–43

    uses op_1628_p3_consecutive_equality_cherry

      intro ϕ hϕ
      exact op_1628_p3_consecutive_equality_cherry ϕ hϕ t ht
  6. 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.

    lines 48–54

    uses Fintype.card_le_of_injective

      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
      omega
  7. 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.

    lines 59–68

    uses op_1628_p3_consecutive_equality_prop_three, le_antisymm, Nat.sInf_le, Nat.sInf_mem, op_1628_p3_consecutive_equality_not_prop_le_two

      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
  8. 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.

    lines 74–75

    uses op_1628_p3_consecutive_equality_number_eq_three

      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)]
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.

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 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)]
See it in the graphDiscuss this resultChallenge it