AFTD Auto-Formalizing Theoretical Domains

op_1628_ramsey_spectrum_consecutive_equality_exists

theoremverifiedformalization

There exists a type V with a Fintype instance, a simple graph G on V such that G is connected and has at least two edges, and natural numbers r, s, t with 1 ≤ t, t < s, and s ≤ r such that set_coloring_ramsey_number G r s t = set_coloring_ramsey_number G r s (t + 1).

Statement

open scoped Classical in
theorem op_1628_ramsey_spectrum_consecutive_equality_exists :
    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),
      G.Connected ∧ 2 ≤ G.edgeFinset.card ∧
      ∃ (r s t : ℕ), 1 ≤ t ∧ t < s ∧ s ≤ r ∧
        set_coloring_ramsey_number G r s t = set_coloring_ramsey_number G r s (t + 1)
Formalizes
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

There exists a finite type $V$ and a simple graph $G$ on $V$ such that: 1. $G$ is connected (G.Connected), 2. $G$ has at least 2 edges (2 ≤ G.edgeFinset.card), and 3. there exist natural numbers $r, s, t$ such that: - $1 \le t$, - $t < s$, - $s \le r$, and - the set-coloring Ramsey number of $G$ with parameters $(r, s, t)$ equals the set-coloring Ramsey number of $G$ with parameters $(r, s, t + 1)$. Here, the set-coloring Ramsey number set_coloring_ramsey_number G r s t is the infimum (sInf, which is the minimum in $\mathbb{N}$, or $0$ if empty) of all natural numbers $N$ such that for every edge-coloring $\phi$ of the complete graph on $\operatorname{Fin} N$ by $s$-element subsets of $\operatorname{Fin} r$ (i.e., $\phi : E(K_N) \to \operatorname{Finset}(\operatorname{Fin} r)$ with $|\phi(e)| = s$ for all edges $e$), there exists a subset $T \subseteq \operatorname{Fin} r$ of size $t$ such that $G$ is contained in the subgraph of $K_N$ formed by the edges whose color sets contain $T$.

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 consecutive equality in the set-coloring Ramsey spectrum, the proof chooses G to be the path graph P₃ on 3 vertices and sets the palette parameters to r = 2, s = 2, and t = 1. Because each edge must be assigned an s-element subset of an r-element palette, every edge receives the entire 2-color palette {0, 1}. Consequently, for both t = 1 and t = 2, any chosen target color set T yields the complete graph K_N as its support graph, making the Ramsey property in both cases equivalent to P₃ embedding into K_N. Since the sets of valid N coincide, their infima—the corresponding Ramsey numbers—are equal.

  1. If every edge of the complete graph has a color set containing T, then the support graph of T is the complete graph.

    By hypothesis h, every edge e of the complete graph ⊤ satisfies T ⊆ ϕ(e). Thus the set of edges whose assigned colors contain T equals the entire edge set of ⊤. Unfolding support_graph and rewriting with this equality and SimpleGraph.fromEdgeSet_edgeSet proves that the support graph is ⊤.

    lines 6–13

    uses SimpleGraph.fromEdgeSet_edgeSet

      have hset : {e : Sym2 (Fin N) | ∃ hh : e ∈ (⊤ : SimpleGraph (Fin N)).edgeSet, T ⊆ ϕ ⟨e, hh⟩}
          = (⊤ : SimpleGraph (Fin N)).edgeSet := by
        ext e
        constructor
        · rintro ⟨hh, -⟩; exact hh
        · intro he; exact ⟨he, h ⟨e, he⟩⟩
      unfold support_graph
      rw [hset, SimpleGraph.fromEdgeSet_edgeSet]
  2. The Ramsey property for G with parameters (r, s, t) = (2, 2, 1) implies that G embeds into the complete graph on N vertices.

    Consider the constant coloring that assigns the entire 2-element palette to every edge. By the assumed Ramsey property, there is a 1-element color set T whose support graph contains G. By op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top, this support graph is the complete graph ⊤, so G is a subgraph of ⊤.

    lines 18–25

    uses op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top

      constructor
      · intro h
        have hϕ : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, ((fun _ => (Finset.univ : Finset (Fin 2))) e).card = 2 := by
          intro e; simp
        obtain ⟨T, hTcard, hTcont⟩ := h (fun _ => Finset.univ) hϕ
        have htop : support_graph (fun _ => (Finset.univ : Finset (Fin 2))) T = (⊤ : SimpleGraph (Fin N)) := by
          apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top; intro e; simp
        rwa [htop] at hTcont
  3. If G embeds into the complete graph on N vertices, then the Ramsey property for G with parameters (2, 2, 1) holds on N vertices.

    Given any edge coloring ϕ assigning 2 colors from a 2-element palette to each edge, every color set ϕ(e) must be the full palette by Finset.eq_univ_of_card. Choosing T = {0}, which has size 1, every edge satisfies {0} ⊆ ϕ(e) by Finset.subset_univ. By op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top, the support graph of {0} is the complete graph ⊤, which contains G by assumption.

    lines 26–34

    uses op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top, Finset.eq_univ_of_card, Finset.subset_univ

      · intro h ϕ hϕ
        refine ⟨{0}, ?_, ?_⟩
        · simp
        · have htop : support_graph ϕ {0} = (⊤ : SimpleGraph (Fin N)) := by
            apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top
            intro e
            have hc : ϕ e = Finset.univ := Finset.eq_univ_of_card _ (by simpa using hϕ e)
            rw [hc]; exact Finset.subset_univ _
          rw [htop]; exact h
  4. The Ramsey property for G with parameters (r, s, t) = (2, 2, 2) implies that G embeds into the complete graph on N vertices.

    Under the coloring assigning the full 2-element palette to every edge, the Ramsey property yields a 2-element set T whose support graph contains G. By op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top, this support graph is the complete graph ⊤, so G is a subgraph of ⊤.

    lines 39–46

    uses op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top

      constructor
      · intro h
        have hϕ : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, ((fun _ => (Finset.univ : Finset (Fin 2))) e).card = 2 := by
          intro e; simp
        obtain ⟨T, hTcard, hTcont⟩ := h (fun _ => Finset.univ) hϕ
        have htop : support_graph (fun _ => (Finset.univ : Finset (Fin 2))) T = (⊤ : SimpleGraph (Fin N)) := by
          apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top; intro e; simp
        rwa [htop] at hTcont
  5. If G embeds into the complete graph on N vertices, then the Ramsey property for G with parameters (2, 2, 2) holds on N vertices.

    Given any coloring ϕ assigning 2 colors from a 2-element palette to each edge, ϕ(e) must be the full palette by Finset.eq_univ_of_card. Taking T to be the full palette gives |T| = 2 with T ⊆ ϕ(e) everywhere, so the support graph is the complete graph ⊤ by op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top. Since G embeds into ⊤, G is contained in the support graph.

    lines 47–55

    uses op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top, Finset.eq_univ_of_card

      · intro h ϕ hϕ
        refine ⟨Finset.univ, ?_, ?_⟩
        · simp
        · have htop : support_graph ϕ (Finset.univ : Finset (Fin 2)) = (⊤ : SimpleGraph (Fin N)) := by
            apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top
            intro e
            have hc : ϕ e = Finset.univ := Finset.eq_univ_of_card _ (by simpa using hϕ e)
            rw [hc]
          rw [htop]; exact h
  6. The pairs s(0, 1) and s(1, 2) are edges of the path graph P₃.

    By SimpleGraph.mem_edgeSet and SimpleGraph.pathGraph_adj, an unordered pair is an edge of the path graph on 3 vertices if and only if the difference between its endpoints is 1. This condition is verified directly for 0 + 1 = 1 and 1 + 1 = 2.

    lines 61–66

    uses SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph_adj

      have h01 : (s(0, 1) : Sym2 (Fin 3)) ∈ (SimpleGraph.pathGraph 3).edgeSet := by
        rw [SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph_adj]
        left; norm_num
      have h12 : (s(1, 2) : Sym2 (Fin 3)) ∈ (SimpleGraph.pathGraph 3).edgeSet := by
        rw [SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph_adj]
        left; norm_num
  7. The edges s(0, 1) and s(1, 2) of P₃ are distinct.

    If s(0, 1) = s(1, 2), then 0 would belong to s(1, 2). By Sym2.mem_iff, this would require 0 = 1 or 0 = 2, both of which are contradictions in Fin 3.

    lines 67–74

    uses Sym2.mem_iff

      have hne : (s(0, 1) : Sym2 (Fin 3)) ≠ s(1, 2) := by
        intro h
        have hm : (0 : Fin 3) ∈ (s(1, 2) : Sym2 (Fin 3)) := by
          rw [← h]; rw [Sym2.mem_iff]; left; rfl
        rw [Sym2.mem_iff] at hm
        rcases hm with h0 | h0
        · exact absurd h0 (by decide)
        · exact absurd h0 (by decide)
  8. The path graph P₃ has at least 2 edges.

    The set {s(0, 1), s(1, 2)} is a subset of the edge set of P₃ by SimpleGraph.mem_edgeFinset, Finset.mem_insert, and Finset.mem_singleton. Since the two edges are distinct, this set has cardinality 2 by Finset.card_pair. Monotonicity of cardinality (Finset.card_le_card) then implies that P₃ has at least 2 edges.

    lines 75–86

    uses SimpleGraph.mem_edgeFinset, Finset.mem_insert, Finset.mem_singleton, Finset.card_pair, Finset.card_le_card

      have hsub : ({s(0, 1), s(1, 2)} : Finset (Sym2 (Fin 3))) ⊆
          @SimpleGraph.edgeFinset (Fin 3) (SimpleGraph.pathGraph 3) i := by
        intro e he
        rw [@SimpleGraph.mem_edgeFinset (Fin 3) (SimpleGraph.pathGraph 3) e i]
        simp only [Finset.mem_insert, Finset.mem_singleton] at he
        rcases he with rfl | rfl
        · exact h01
        · exact h12
      have hcard : ({s(0, 1), s(1, 2)} : Finset (Sym2 (Fin 3))).card = 2 := Finset.card_pair hne
      have hle := Finset.card_le_card hsub
      rw [hcard] at hle
      exact hle
  9. The path graph P₃ on vertices Fin 3 is connected, has at least 2 edges, and parameters (r, s, t) = (2, 2, 1) satisfy 1 ≤ t < s ≤ r.

    Instantiate the existential witnesses with V = Fin 3, G = P₃, r = 2, s = 2, and t = 1. Connectedness follows from SimpleGraph.pathGraph_connected 2, the edge count bound 2 ≤ |E(P₃)| from op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset, and the parameter inequalities 1 ≤ 1, 1 < 2, and 2 ≤ 2 by numerical computation.

    lines 95–101

    uses SimpleGraph.pathGraph_connected, op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset

      refine ⟨Fin 3, inferInstance, SimpleGraph.pathGraph 3, ?_, ?_, 2, 2, 1, ?_, ?_, ?_, ?_⟩
      · have := SimpleGraph.pathGraph_connected 2
        simpa using this
      · exact op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset _
      · norm_num
      · norm_num
      · norm_num
  10. The Ramsey numbers for parameters (2, 2, 1) and (2, 2, 2) on P₃ are equal.

    Each Ramsey number is defined as the infimum of the set of graph sizes N for which the corresponding Ramsey property holds. By op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff and op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff, both properties are equivalent to P₃ being contained in the complete graph on N vertices. The sets of valid N are therefore identical, so their infima are equal.

    lines 102–109

    uses op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff, op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff

      · show sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 1 N}
           = sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 2 N}
        have hset : {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 1 N}
            = {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 2 N} := by
          ext N
          exact (op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff (N := N) _).trans
            (op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff (N := N) _).symm
        rw [hset]
SimpleGraph.fromEdgeSet_edgeSet
The graph reconstructed from its edge set is the graph itself.
op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top
If every edge of the complete graph has a color set containing T, then the support graph of T is the complete graph.
Finset.eq_univ_of_card
A finset of a finite type whose cardinality equals that of the entire type is the universal finset.
Finset.subset_univ
Every finset of a finite type is a subset of the universal finset.
SimpleGraph.mem_edgeSet
An unordered pair belongs to the edge set of a graph if and only if its endpoints are adjacent.
SimpleGraph.pathGraph_adj
Two vertices in a path graph are adjacent if and only if their indices differ by 1.
Sym2.mem_iff
An element belongs to an unordered pair s(b, c) if and only if it equals b or c.
SimpleGraph.mem_edgeFinset
An element belongs to the edge finset of a graph if and only if it belongs to its edge set.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.card_pair
A pair of distinct elements has cardinality 2.
Finset.card_le_card
If s is a subset of t, then the cardinality of s is at most that of t.
SimpleGraph.pathGraph_connected
The path graph on n + 1 vertices is connected.
op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset
The path graph on 3 vertices has at least 2 edges.
op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff
The Ramsey property for parameters (2, 2, 1) holds for a 3-vertex graph G on N vertices if and only if G embeds into the complete graph on N vertices.
op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff
The Ramsey property for parameters (2, 2, 2) holds for a 3-vertex graph G on N vertices if and only if G embeds into the complete graph on N vertices.

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 inlemma op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top {N r : ℕ}    (ϕ : (⊤ : SimpleGraph (Fin N)).edgeSet → Finset (Fin r))    (T : Finset (Fin r)) (h : ∀ e, T ⊆ ϕ e) :    support_graph ϕ T = (⊤ : SimpleGraph (Fin N)) := by  have hset : {e : Sym2 (Fin N) | ∃ hh : e ∈ (⊤ : SimpleGraph (Fin N)).edgeSet, T ⊆ ϕ ⟨e, hh⟩}      = (⊤ : SimpleGraph (Fin N)).edgeSet := by    ext e    constructor    · rintro ⟨hh, -⟩; exact hh    · intro he; exact ⟨he, h ⟨e, he⟩⟩  unfold support_graph  rw [hset, SimpleGraph.fromEdgeSet_edgeSet]open scoped Classical inlemma op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff {N : ℕ} (G : SimpleGraph (Fin 3)) :    set_coloring_ramsey_property G 2 2 1 N ↔ SimpleGraph.IsContained G (⊤ : SimpleGraph (Fin N)) := by  constructor  · intro h    have hϕ : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, ((fun _ => (Finset.univ : Finset (Fin 2))) e).card = 2 := by      intro e; simp    obtain ⟨T, hTcard, hTcont⟩ := h (fun _ => Finset.univ) hϕ    have htop : support_graph (fun _ => (Finset.univ : Finset (Fin 2))) T = (⊤ : SimpleGraph (Fin N)) := by      apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top; intro e; simp    rwa [htop] at hTcont  · intro h ϕ hϕ    refine ⟨{0}, ?_, ?_⟩    · simp    · have htop : support_graph ϕ {0} = (⊤ : SimpleGraph (Fin N)) := by        apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top        intro e        have hc : ϕ e = Finset.univ := Finset.eq_univ_of_card _ (by simpa using hϕ e)        rw [hc]; exact Finset.subset_univ _      rw [htop]; exact hopen scoped Classical inlemma op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff {N : ℕ} (G : SimpleGraph (Fin 3)) :    set_coloring_ramsey_property G 2 2 2 N ↔ SimpleGraph.IsContained G (⊤ : SimpleGraph (Fin N)) := by  constructor  · intro h    have hϕ : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, ((fun _ => (Finset.univ : Finset (Fin 2))) e).card = 2 := by      intro e; simp    obtain ⟨T, hTcard, hTcont⟩ := h (fun _ => Finset.univ) hϕ    have htop : support_graph (fun _ => (Finset.univ : Finset (Fin 2))) T = (⊤ : SimpleGraph (Fin N)) := by      apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top; intro e; simp    rwa [htop] at hTcont  · intro h ϕ hϕ    refine ⟨Finset.univ, ?_, ?_⟩    · simp    · have htop : support_graph ϕ (Finset.univ : Finset (Fin 2)) = (⊤ : SimpleGraph (Fin N)) := by        apply op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_top        intro e        have hc : ϕ e = Finset.univ := Finset.eq_univ_of_card _ (by simpa using hϕ e)        rw [hc]      rw [htop]; exact hopen scoped Classical inlemma op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset    (i : Fintype ↑(SimpleGraph.pathGraph 3).edgeSet) :    2 ≤ (@SimpleGraph.edgeFinset (Fin 3) (SimpleGraph.pathGraph 3) i).card := by  have h01 : (s(0, 1) : Sym2 (Fin 3)) ∈ (SimpleGraph.pathGraph 3).edgeSet := by    rw [SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph_adj]    left; norm_num  have h12 : (s(1, 2) : Sym2 (Fin 3)) ∈ (SimpleGraph.pathGraph 3).edgeSet := by    rw [SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph_adj]    left; norm_num  have hne : (s(0, 1) : Sym2 (Fin 3)) ≠ s(1, 2) := by    intro h    have hm : (0 : Fin 3) ∈ (s(1, 2) : Sym2 (Fin 3)) := by      rw [← h]; rw [Sym2.mem_iff]; left; rfl    rw [Sym2.mem_iff] at hm    rcases hm with h0 | h0    · exact absurd h0 (by decide)    · exact absurd h0 (by decide)  have hsub : ({s(0, 1), s(1, 2)} : Finset (Sym2 (Fin 3))) ⊆      @SimpleGraph.edgeFinset (Fin 3) (SimpleGraph.pathGraph 3) i := by    intro e he    rw [@SimpleGraph.mem_edgeFinset (Fin 3) (SimpleGraph.pathGraph 3) e i]    simp only [Finset.mem_insert, Finset.mem_singleton] at he    rcases he with rfl | rfl    · exact h01    · exact h12  have hcard : ({s(0, 1), s(1, 2)} : Finset (Sym2 (Fin 3))).card = 2 := Finset.card_pair hne  have hle := Finset.card_le_card hsub  rw [hcard] at hle  exact hleopen scoped Classical in/-- Existence of a connected graph with at least two edges and palette parameters yielding equality in consecutive terms of the Ramsey intersection spectrum. -/theorem op_1628_ramsey_spectrum_consecutive_equality_exists :    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),      G.Connected ∧ 2 ≤ G.edgeFinset.card ∧      ∃ (r s t : ℕ), 1 ≤ t ∧ t < s ∧ s ≤ r ∧        set_coloring_ramsey_number G r s t = set_coloring_ramsey_number G r s (t + 1) := by  refine ⟨Fin 3, inferInstance, SimpleGraph.pathGraph 3, ?_, ?_, 2, 2, 1, ?_, ?_, ?_, ?_⟩  · have := SimpleGraph.pathGraph_connected 2    simpa using this  · exact op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinset _  · norm_num  · norm_num  · norm_num  · show sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 1 N}       = sInf {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 2 N}    have hset : {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 1 N}        = {N : ℕ | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) 2 2 2 N} := by      ext N      exact (op_1628_ramsey_spectrum_consecutive_equality_exists_prop_one_iff (N := N) _).trans        (op_1628_ramsey_spectrum_consecutive_equality_exists_prop_two_iff (N := N) _).symm    rw [hset]
See it in the graphDiscuss this resultChallenge it