op_1628_ramsey_spectrum_consecutive_equality_exists
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.
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 ⊤.
uses
SimpleGraph.fromEdgeSet_edgeSethave 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]
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 ⊤.
uses
op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_topconstructor · 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
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.
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
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 ⊤.
uses
op_1628_ramsey_spectrum_consecutive_equality_exists_support_graph_eq_topconstructor · 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
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.
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
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.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.pathGraph_adjhave 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
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.
uses
Sym2.mem_iffhave 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)
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.
uses
SimpleGraph.mem_edgeFinset,Finset.mem_insert,Finset.mem_singleton,Finset.card_pair,Finset.card_le_cardhave 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
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.
uses
SimpleGraph.pathGraph_connected,op_1628_ramsey_spectrum_consecutive_equality_exists_two_le_pathGraph_edgeFinsetrefine ⟨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
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.
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
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 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]