op_1258_cyclic_ramsey_k_one
For every integer l ≥ 3, the cyclic Ramsey number R_cyc(NM_2, MP_l) of the 1-edge nested matching and the monotone path MP_l equals l.
Statement
theorem op_1258_cyclic_ramsey_k_one (l : ℕ) (hl : 3 ≤ l) :
cyclic_ramsey_number (nested_matching 1) (monotone_path l) = l- Formalizes
- arXiv:2611.08375, Sec. 3.4
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- nested_matchingThe nested matching NM_{2k} is the cyclically ordered simple graph on 2k vertices with edges {i, 2k - 1 - i} for 0 ≤ i < k.
- monotone_pathThe monotone path MP_l is the cyclically ordered simple graph on l vertices with edges between consecutive vertices i and i + 1 for 0 ≤ i…
- cyclic_ramsey_numberThe cyclic Ramsey number R_cyc(H₁, H₂) is the smallest positive integer N such that every 2-edge-colouring of the complete cyclically…
- cyclic_ramsey_propertycyclic_ramsey_property H₁ H₂ N holds if every red/blue edge-colouring of K_N contains a red cyclic copy of H₁ or a blue cyclic copy of H₂,…
- cyclic_has_copyA cyclically ordered graph G on Fin N contains a cyclically ordered copy of H on Fin m if there is an injective graph homomorphism from H…
Read back from the Lean
For every natural number $l$ satisfying $l \ge 3$, the cyclic Ramsey number of the nested matching graph with parameter $k = 1$ and the monotone path graph on $l$ vertices is equal to $l$.
Here:
- The cyclic Ramsey number of two graphs $H_1$ on $\mathrm{Fin}(m)$ and $H_2$ on $\mathrm{Fin}(n)$ is the least positive integer $N$ such that every simple graph $G$ on $\mathrm{Fin}(N)$ has a cyclic-order-preserving copy of $H_1$, or its complement $G^c$ has a cyclic-order-preserving copy of $H_2$.
- A cyclic-order-preserving copy of $H$ in $G$ is an injective graph homomorphism $f : V(H) \to V(G)$ that preserves the cyclic order (the strict betweenness relation sbtw).
- nested_matching 1 is the graph on $\mathrm{Fin}(2)$ with an edge between 0 and 1.
- monotone_path l is the path graph on $\mathrm{Fin}(l)$ with edges $\{i, i+1\}$ for $0 \le i < l - 1$.
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 cyclic Ramsey number R_cyc(NM₂, MP_l) is the least positive integer N such that every graph on N vertices contains a cyclic copy of the 1-edge nested matching NM₂ or its complement contains a cyclic copy of the monotone path MP_l. At N = l, any graph either contains an edge (giving a cyclic copy of NM₂) or is empty, in which case its complement is complete and embeds MP_l; thus the Ramsey property holds at l. Conversely, for any N < l, the empty graph witnesses that the property fails: it has no edges, and its complete complement has too few vertices (N < l) to embed the l-vertex path MP_l. Since l satisfies the property and no smaller integer does, the infimum is exactly l.
A cyclic copy of a graph on m vertices in a graph on N vertices forces m ≤ N.
A cyclic embedding of a graph on m vertices into one on N vertices includes an injective vertex map f : Fin m → Fin N. By Fintype.card_le_of_injective, the cardinality of the domain is at most the cardinality of the codomain, which simplifies to m ≤ N.
uses
Fintype.card_le_of_injectiveobtain ⟨f, hf, _⟩ := h simpa using Fintype.card_le_of_injective f hf
The empty graph on N vertices contains no cyclic copy of the 1-edge nested matching NM₂.
Suppose for contradiction that an embedding f exists. In the one-edge nested matching NM₂, vertices 0 and 1 are adjacent by definition. Since an embedding preserves edges, f(0) and f(1) must be adjacent in the empty graph ⊥. But by SimpleGraph.bot_adj, no two vertices are adjacent in ⊥, giving False.
uses
SimpleGraph.bot_adjrintro ⟨f, _, hadj, _⟩ have h01 : (nested_matching 1).Adj (0 : Fin 2) 1 := by simp [nested_matching, SimpleGraph.fromRel] have h := hadj h01 simp [SimpleGraph.bot_adj] at h
Any graph containing an edge contains a cyclic copy of the 1-edge nested matching NM₂.
Let u and v be adjacent vertices in G. Define f = ![u, v] mapping the two vertices of NM₂ to u and v. This map is injective because adjacent vertices are distinct (u ≠ v). It preserves edges because u ~ v and v ~ u by symmetry. Finally, cyclic betweenness is preserved vacuously, because no three distinct elements exist in Fin 2, so the condition sbtw_iff cannot be satisfied.
uses
sbtw_iffhave huvne : u ≠ v := huv.ne have hvu : G.Adj v u := huv.symm refine ⟨![u, v], ?_, ?_, ?_⟩ · intro a b hab fin_cases a <;> fin_cases b <;> simp_all · intro a b hab fin_cases a <;> fin_cases b <;> simp_all [nested_matching, SimpleGraph.fromRel] · intro a b c hab rw [sbtw_iff] at hab omega
The complete graph on N ≥ l vertices contains a cyclic copy of the monotone path MP_l.
The canonical inclusion Fin.castLE embeds MP_l into the complete graph ⊤: it is injective by Fin.castLE_injective, preserves adjacency because any two distinct vertices are adjacent in ⊤ (SimpleGraph.top_adj), and preserves cyclic order because Fin.castLE preserves the natural order on indices (Fin.lt_def, Fin.val_castLE, sbtw_iff).
uses
Fin.castLE_injective,SimpleGraph.top_adj,sbtw_iff,Fin.lt_def,Fin.val_castLErefine ⟨Fin.castLE h, Fin.castLE_injective h, ?_, ?_⟩ · intro u v huv simp only [SimpleGraph.top_adj] exact fun heq => huv.ne (Fin.castLE_injective h heq) · intro u v w hb simpa only [sbtw_iff, Fin.lt_def, Fin.val_castLE] using hb
If a graph on l vertices has at least one edge, it contains a cyclic copy of NM₂.
Given an arbitrary graph G on l vertices, we test whether G has an edge. If there exist adjacent vertices u ~ v, then op_1258_cyclic_ramsey_k_one_edge_copy immediately yields a cyclic copy of NM₂ in G.
uses
op_1258_cyclic_ramsey_k_one_edge_copyintro G by_cases h : ∃ u v, G.Adj u v · left obtain ⟨u, v, huv⟩ := h exact op_1258_cyclic_ramsey_k_one_edge_copy l G u v huv
If a graph on l vertices has no edges, its complement contains a cyclic copy of MP_l.
If G has no edges, then by extensionality G = ⊥, using SimpleGraph.bot_adj. Its complement Gᶜ is therefore the complete graph ⊤ on l vertices. By op_1258_cyclic_ramsey_k_one_monotone_top with N = l (and le_rfl), ⊤ contains a cyclic copy of MP_l.
uses
SimpleGraph.bot_adj,op_1258_cyclic_ramsey_k_one_monotone_top,le_rfl· right have hbot : G = ⊥ := by ext u v simp only [SimpleGraph.bot_adj] constructor · intro huv; exact absurd ⟨u, v, huv⟩ h · intro hf; exact hf.elim rw [hbot] simpa using op_1258_cyclic_ramsey_k_one_monotone_top (l := l) (N := l) le_rfl
For every N < l, the cyclic Ramsey property fails.
Suppose for contradiction that the cyclic Ramsey property holds at N < l. Testing it on the empty graph ⊥ on N vertices, either ⊥ contains a cyclic copy of NM₂, or its complement ⊤ contains a cyclic copy of MP_l. The first case is impossible by op_1258_cyclic_ramsey_k_one_not_copy_bot. The second case requires l ≤ N by op_1258_cyclic_ramsey_k_one_vertex_bound, which contradicts N < l.
uses
op_1258_cyclic_ramsey_k_one_not_copy_bot,op_1258_cyclic_ramsey_k_one_vertex_boundintro hp have h' := hp (⊥ : SimpleGraph (Fin N)) rcases h' with h1 | h2 · exact op_1258_cyclic_ramsey_k_one_not_copy_bot h1 · have hbot : (⊥ : SimpleGraph (Fin N))ᶜ = ⊤ := by simp rw [hbot] at h2 have hle := op_1258_cyclic_ramsey_k_one_vertex_bound h2 omega
The cyclic Ramsey number of NM₂ and MP_l is at most l.
By definition, the cyclic Ramsey number is the infimum of the set of positive integers N satisfying the cyclic Ramsey property. Since l ≥ 3 > 0 and the property holds at l by op_1258_cyclic_ramsey_k_one_property, l belongs to this set. Therefore, the infimum is at most l by Nat.sInf_le, and proving equality reduces via le_antisymm to showing l ≤ the infimum.
uses
op_1258_cyclic_ramsey_k_one_property,Nat.sInf_le,le_antisymmunfold cyclic_ramsey_number have hmem : l ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} := ⟨by omega, op_1258_cyclic_ramsey_k_one_property l⟩ refine le_antisymm (Nat.sInf_le hmem) ?_
The cyclic Ramsey number of NM₂ and MP_l is at least l, and therefore equals l.
Suppose for contradiction that the infimum were strictly less than l (using not_le). Since the set is nonempty, its infimum belongs to the set by Nat.sInf_mem, meaning the cyclic Ramsey property holds at that infimum. But this contradicts op_1258_cyclic_ramsey_k_one_not_property, which establishes that the property fails for all N < l. Thus the infimum must equal l.
uses
not_le,Nat.sInf_mem,op_1258_cyclic_ramsey_k_one_not_propertyby_contra hcon rw [not_le] at hcon have hinf : sInf {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} := Nat.sInf_mem ⟨l, hmem⟩ exact op_1258_cyclic_ramsey_k_one_not_property hcon hinf.2
Fintype.card_le_of_injective- An injective map between finite types forces the cardinality of the domain to be at most that of the codomain.
SimpleGraph.bot_adj- No two vertices are adjacent in the empty graph (bot).
sbtw_iff- Strict cyclic betweenness sbtw a b c holds if and only if the three elements are cyclically ordered: a < b < c, b < c < a, or c < a < b.
Fin.castLE_injective- The canonical inclusion Fin.castLE from Fin n into Fin m for n ≤ m is injective.
SimpleGraph.top_adj- Two vertices in the complete graph (top) are adjacent if and only if they are distinct.
Fin.lt_def- The strict order on Fin n agrees with the strict order on the underlying natural numbers.
Fin.val_castLE- The canonical inclusion Fin.castLE preserves the underlying natural number value of an index.
op_1258_cyclic_ramsey_k_one_edge_copy- Any graph containing an edge contains a cyclic copy of the one-edge nested matching NM₂.
op_1258_cyclic_ramsey_k_one_monotone_top- The complete graph on N ≥ l vertices contains a cyclic copy of the monotone path MP_l.
le_rfl- The order relation ≤ is reflexive: a ≤ a for every a.
op_1258_cyclic_ramsey_k_one_not_copy_bot- The empty graph contains no cyclic copy of the one-edge nested matching NM₂.
op_1258_cyclic_ramsey_k_one_vertex_bound- If a graph on N vertices contains a cyclic copy of a graph on m vertices, then m ≤ N.
op_1258_cyclic_ramsey_k_one_property- The cyclic Ramsey property holds at N = l: every graph on l vertices contains a cyclic copy of NM₂ or its complement contains a cyclic copy of MP_l.
le_antisymm- A partial order is antisymmetric: if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element in the set.
not_le- In a linear order, a is not at most b if and only if b < a.
Nat.sInf_mem- If a set of natural numbers is nonempty, its infimum belongs to the set.
op_1258_cyclic_ramsey_k_one_not_property- For every N < l, the cyclic Ramsey property fails for NM₂ and MP_l.
- Because the one-edge nested matching NM₂ has only 2 vertices, the cyclic order-preserving condition is vacuously satisfied for any embedding into another graph; in the formalization, this fact is closed via linear arithmetic (omega).
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 SimpleGraph/-- A cyclic copy of a graph on `m` vertices into a graph on `N` vertices forces `m ≤ N`. -/private lemma op_1258_cyclic_ramsey_k_one_vertex_bound {m N : ℕ} {H : SimpleGraph (Fin m)} {G : SimpleGraph (Fin N)} (h : cyclic_has_copy H G) : m ≤ N := by obtain ⟨f, hf, _⟩ := h simpa using Fintype.card_le_of_injective f hf/-- The empty graph contains no cyclic copy of the one-edge nested matching. -/private lemma op_1258_cyclic_ramsey_k_one_not_copy_bot {N : ℕ} : ¬ cyclic_has_copy (nested_matching 1) (⊥ : SimpleGraph (Fin N)) := by rintro ⟨f, _, hadj, _⟩ have h01 : (nested_matching 1).Adj (0 : Fin 2) 1 := by simp [nested_matching, SimpleGraph.fromRel] have h := hadj h01 simp [SimpleGraph.bot_adj] at h/-- Any graph with an edge contains a cyclic copy of the one-edge nested matching. -/private lemma op_1258_cyclic_ramsey_k_one_edge_copy (l : ℕ) (G : SimpleGraph (Fin l)) (u v : Fin l) (huv : G.Adj u v) : cyclic_has_copy (nested_matching 1) G := by have huvne : u ≠ v := huv.ne have hvu : G.Adj v u := huv.symm refine ⟨![u, v], ?_, ?_, ?_⟩ · intro a b hab fin_cases a <;> fin_cases b <;> simp_all · intro a b hab fin_cases a <;> fin_cases b <;> simp_all [nested_matching, SimpleGraph.fromRel] · intro a b c hab rw [sbtw_iff] at hab omega/-- The complete graph on `N ≥ l` vertices contains a cyclic copy of the monotone path `MP_l`. -/private lemma op_1258_cyclic_ramsey_k_one_monotone_top {l N : ℕ} (h : l ≤ N) : cyclic_has_copy (monotone_path l) (⊤ : SimpleGraph (Fin N)) := by refine ⟨Fin.castLE h, Fin.castLE_injective h, ?_, ?_⟩ · intro u v huv simp only [SimpleGraph.top_adj] exact fun heq => huv.ne (Fin.castLE_injective h heq) · intro u v w hb simpa only [sbtw_iff, Fin.lt_def, Fin.val_castLE] using hb/-- The cyclic Ramsey property holds at `N = l`: every edge-colouring of `K_l` has a redsingle edge or a blue cyclic monotone path `MP_l`. -/private lemma op_1258_cyclic_ramsey_k_one_property (l : ℕ) : cyclic_ramsey_property (nested_matching 1) (monotone_path l) l := by intro G by_cases h : ∃ u v, G.Adj u v · left obtain ⟨u, v, huv⟩ := h exact op_1258_cyclic_ramsey_k_one_edge_copy l G u v huv · right have hbot : G = ⊥ := by ext u v simp only [SimpleGraph.bot_adj] constructor · intro huv; exact absurd ⟨u, v, huv⟩ h · intro hf; exact hf.elim rw [hbot] simpa using op_1258_cyclic_ramsey_k_one_monotone_top (l := l) (N := l) le_rfl/-- For every `N < l` the cyclic Ramsey property fails, witnessed by the empty graph. -/private lemma op_1258_cyclic_ramsey_k_one_not_property {l N : ℕ} (hN : N < l) : ¬ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N := by intro hp have h' := hp (⊥ : SimpleGraph (Fin N)) rcases h' with h1 | h2 · exact op_1258_cyclic_ramsey_k_one_not_copy_bot h1 · have hbot : (⊥ : SimpleGraph (Fin N))ᶜ = ⊤ := by simp rw [hbot] at h2 have hle := op_1258_cyclic_ramsey_k_one_vertex_bound h2 omega/-- The k = 1 case of Conjecture 4.32: R_cyc(NM_2, MP_l) = l. -/theorem op_1258_cyclic_ramsey_k_one (l : ℕ) (hl : 3 ≤ l) : cyclic_ramsey_number (nested_matching 1) (monotone_path l) = l := by unfold cyclic_ramsey_number have hmem : l ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} := ⟨by omega, op_1258_cyclic_ramsey_k_one_property l⟩ refine le_antisymm (Nat.sInf_le hmem) ?_ by_contra hcon rw [not_le] at hcon have hinf : sInf {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 1) (monotone_path l) N} := Nat.sInf_mem ⟨l, hmem⟩ exact op_1258_cyclic_ramsey_k_one_not_property hcon hinf.2