op_1258_cyclic_ramsey_k2_l3
The cyclic Ramsey number R_cyc(NM_4, MP_3) of the 2-edge nested matching NM_4 and the monotone path MP_3 is equal to 4.
Statement
theorem op_1258_cyclic_ramsey_k2_l3 :
cyclic_ramsey_number (nested_matching 2) (monotone_path 3) = 4- Formalizes
- arXiv:2611.08375, Table 1
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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…
- 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₂,…
- strictStrict preference derived from a weak preference relation.
Read back from the Lean
The cyclic Ramsey number of the nested matching of size 2 and the monotone path of length 3 (with 3 vertices) is equal to 4. That is, the least positive integer $N$ such that every simple graph $G$ on $\text{Fin } N$ either has a cyclic copy of the nested matching on 4 vertices or its complement $G^c$ has a cyclic copy of the 3-vertex monotone path, is 4.
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 prove that the cyclic Ramsey number R_cyc(NM_4, MP_3) equals 4, we show that 4 has the cyclic Ramsey property and no N < 4 does. On 4 vertices, a propositional case analysis on the four cycle edges shows that any graph G either contains two opposite edges—yielding a cyclic copy of the nested matching NM_4—or its complement Gᶜ contains two consecutive edges, which form a cyclic monotone path MP_3 of length 2. For N < 4, the property fails on the complete graph ⊤ because NM_4 requires at least 4 vertices by injectivity, while ⊤ᶜ has no edges to support MP_3.
Cyclic rotation on Fin 4 and shifted embedding from Fin 3 to Fin 4 are well-defined. automation
Strict betweenness on Fin n is declared decidable by expressing it in terms of the linear order on Fin n. The rotation map u ↦ (j + u) mod 4 on Fin 4 and the shifted embedding from Fin 3 to Fin 4 are defined, with the modular bounds (j + u) mod 4 < 4 verified by linear arithmetic (`omega`).
uses
decidable_of_iff,Iff.rfl/-- Decidability of strict betweenness on `Fin n`, through the linear-order instance. -/ instance op_1258_cyclic_ramsey_k2_l3_instDecidableSBtwFin {n : ℕ} (a b c : Fin n) : Decidable (sbtw a b c) := decidable_of_iff (a < b ∧ b < c ∨ b < c ∧ c < a ∨ c < a ∧ a < b) Iff.rfl /-- Rotation of the cyclic order on `Fin 4` by `j`. -/ def op_1258_cyclic_ramsey_k2_l3_rot4 (j u : Fin 4) : Fin 4 := ⟨(j.val + u.val) % 4, by omega⟩ /-- Rotation of `Fin 3` into the cyclic order on `Fin 4` by `j`. -/ def op_1258_cyclic_ramsey_k2_l3_rot34 (j : Fin 4) (u : Fin 3) : Fin 4 := ⟨(j.val + u.val) % 4, by omega⟩
The cyclic rotations and shifted embeddings are injective and preserve cyclic strict betweenness. automation
Four helper lemmas establish that rot4 j is injective and order-preserving on Fin 4, and rot34 j is injective and order-preserving from Fin 3 to Fin 4. Since the vertex sets are finite, each lemma is proven by exhaustive computation (`decide`).
lemma op_1258_cyclic_ramsey_k2_l3_rot4_inj : ∀ j : Fin 4, Function.Injective (op_1258_cyclic_ramsey_k2_l3_rot4 j) := by decide lemma op_1258_cyclic_ramsey_k2_l3_rot4_sbtw : ∀ (j u v w : Fin 4), sbtw u v w → sbtw (op_1258_cyclic_ramsey_k2_l3_rot4 j u) (op_1258_cyclic_ramsey_k2_l3_rot4 j v) (op_1258_cyclic_ramsey_k2_l3_rot4 j w) := by decide lemma op_1258_cyclic_ramsey_k2_l3_rot34_inj : ∀ j : Fin 4, Function.Injective (op_1258_cyclic_ramsey_k2_l3_rot34 j) := by decide lemma op_1258_cyclic_ramsey_k2_l3_rot34_sbtw : ∀ (j : Fin 4) (u v w : Fin 3), sbtw u v w → sbtw (op_1258_cyclic_ramsey_k2_l3_rot34 j u) (op_1258_cyclic_ramsey_k2_l3_rot34 j v) (op_1258_cyclic_ramsey_k2_l3_rot34 j w) := by decide
The edges of NM_4 are {0, 3} and {1, 2}, and the edges of MP_3 are {0, 1} and {1, 2}.
By definition, the edges of NM_4 (nested matching of order 2) satisfy u + v + 1 = 4, and the edges of MP_3 (monotone path of length 2) satisfy u + 1 = v (up to symmetry). Exhaustive case analysis on all pairs of vertices (`fin_cases`) and simplification (`simp_all`) enumerates every possible edge.
uses
SimpleGraph.fromRel/-- The edges of `NM_4` are `{0,3}` and `{1,2}`. -/ lemma op_1258_cyclic_ramsey_k2_l3_nm4_cases {u v : Fin 4} (h : (nested_matching 2).Adj u v) : (u = 0 ∧ v = 3) ∨ (u = 3 ∧ v = 0) ∨ (u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1) := by fin_cases u <;> fin_cases v <;> simp_all [nested_matching, SimpleGraph.fromRel] /-- The edges of `MP_3` are `{0,1}` and `{1,2}`. -/ lemma op_1258_cyclic_ramsey_k2_l3_mp3_cases {u v : Fin 3} (h : (monotone_path 3).Adj u v) : (u = 0 ∧ v = 1) ∨ (u = 1 ∧ v = 0) ∨ (u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1) := by fin_cases u <;> fin_cases v <;> simp_all [monotone_path, SimpleGraph.fromRel]
Any graph on 4 vertices containing two opposite edges of the 4-cycle contains a cyclic copy of NM_4.
If a graph G on Fin 4 contains the opposite edges {0, 3} and {1, 2}, the identity rotation rot4 0 provides an embedding of NM_4 into G. If G contains the rotated opposite pair {0, 1} and {2, 3}, the shift rot4 1 provides the embedding. In each case, injectivity and betweenness preservation follow from the rotation properties, and the edges map correctly by edge classification of NM_4 and graph symmetry (`SimpleGraph.adj_comm`).
uses
op_1258_cyclic_ramsey_k2_l3_rot4_inj,op_1258_cyclic_ramsey_k2_l3_rot4_sbtw,op_1258_cyclic_ramsey_k2_l3_nm4_cases,SimpleGraph.adj_comm/-- Two nested edges `03` and `12` form a cyclic copy of `NM_4`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0 (G : SimpleGraph (Fin 4)) (h03 : G.Adj 0 3) (h12 : G.Adj 1 2) : cyclic_has_copy (nested_matching 2) G := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot4 0, op_1258_cyclic_ramsey_k2_l3_rot4_inj 0, ?_, op_1258_cyclic_ramsey_k2_l3_rot4_sbtw 0⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_nm4_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h03 · exact (SimpleGraph.adj_comm G 0 3).1 h03 · exact h12 · exact (SimpleGraph.adj_comm G 1 2).1 h12 /-- The rotated edges `01` and `23` form a cyclic copy of `NM_4`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1 (G : SimpleGraph (Fin 4)) (h01 : G.Adj 0 1) (h23 : G.Adj 2 3) : cyclic_has_copy (nested_matching 2) G := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot4 1, op_1258_cyclic_ramsey_k2_l3_rot4_inj 1, ?_, op_1258_cyclic_ramsey_k2_l3_rot4_sbtw 1⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_nm4_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact (SimpleGraph.adj_comm G 0 1).1 h01 · exact h01 · exact h23 · exact (SimpleGraph.adj_comm G 2 3).1 h23
Any graph on 4 vertices containing two consecutive edges along the 4-cycle contains a cyclic copy of MP_3.
For each of the four possible 2-edge paths along the cyclic boundary—(0, 1, 2), (1, 2, 3), (2, 3, 0), and (3, 0, 1)—the shifted embeddings rot34 0, rot34 1, rot34 2, and rot34 3 respectively map the monotone path 0-1-2 into H while preserving injectivity, cyclic betweenness, and graph adjacency.
uses
op_1258_cyclic_ramsey_k2_l3_rot34_inj,op_1258_cyclic_ramsey_k2_l3_rot34_sbtw,op_1258_cyclic_ramsey_k2_l3_mp3_cases,SimpleGraph.adj_comm/-- The cyclic path `0-1-2` in `H` is a copy of `MP_3`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0 (H : SimpleGraph (Fin 4)) (h01 : H.Adj 0 1) (h12 : H.Adj 1 2) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 0, op_1258_cyclic_ramsey_k2_l3_rot34_inj 0, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 0⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h01 · exact (SimpleGraph.adj_comm H 0 1).1 h01 · exact h12 · exact (SimpleGraph.adj_comm H 1 2).1 h12 /-- The cyclic path `1-2-3` in `H` is a copy of `MP_3`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1 (H : SimpleGraph (Fin 4)) (h12 : H.Adj 1 2) (h23 : H.Adj 2 3) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 1, op_1258_cyclic_ramsey_k2_l3_rot34_inj 1, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 1⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h12 · exact (SimpleGraph.adj_comm H 1 2).1 h12 · exact h23 · exact (SimpleGraph.adj_comm H 2 3).1 h23 /-- The cyclic path `2-3-0` in `H` is a copy of `MP_3`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2 (H : SimpleGraph (Fin 4)) (h23 : H.Adj 2 3) (h30 : H.Adj 3 0) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 2, op_1258_cyclic_ramsey_k2_l3_rot34_inj 2, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 2⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h23 · exact (SimpleGraph.adj_comm H 2 3).1 h23 · exact h30 · exact (SimpleGraph.adj_comm H 3 0).1 h30 /-- The cyclic path `3-0-1` in `H` is a copy of `MP_3`. -/ lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3 (H : SimpleGraph (Fin 4)) (h30 : H.Adj 3 0) (h01 : H.Adj 0 1) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 3, op_1258_cyclic_ramsey_k2_l3_rot34_inj 3, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 3⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h30 · exact (SimpleGraph.adj_comm H 3 0).1 h30 · exact h01 · exact (SimpleGraph.adj_comm H 0 1).1 h01
Every 2-colouring of K_4 contains a cyclic copy of NM_4 in G or a cyclic copy of MP_3 in Gᶜ.
Given any graph G on Fin 4, propositional logic (`tauto`) guarantees that among the four cyclic boundary edges {0, 1}, {1, 2}, {2, 3}, {3, 0}, either two opposite edges belong to G or two consecutive edges do not belong to G. If two opposite edges are in G, G contains a cyclic copy of NM_4. If two consecutive edges are not in G, they belong to the complement Gᶜ by definition (`SimpleGraph.compl_adj`), so Gᶜ contains a cyclic copy of MP_3.
uses
SimpleGraph.compl_adj,Or.inl,Or.inr,op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1,op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0,SimpleGraph.adj_comm,op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0,op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1,op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2,op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3/-- Every `2`-colouring of the cyclically ordered `K_4` contains a monochromatic copy of `NM_4` or of `MP_3`: a propositional case analysis on the four edges of the `4`-cycle. -/ lemma op_1258_cyclic_ramsey_k2_l3_property_four : cyclic_ramsey_property (nested_matching 2) (monotone_path 3) 4 := by intro G have key : (G.Adj 0 1 ∧ G.Adj 2 3) ∨ (G.Adj 3 0 ∧ G.Adj 1 2) ∨ (¬ G.Adj 0 1 ∧ ¬ G.Adj 1 2) ∨ (¬ G.Adj 1 2 ∧ ¬ G.Adj 2 3) ∨ (¬ G.Adj 2 3 ∧ ¬ G.Adj 3 0) ∨ (¬ G.Adj 3 0 ∧ ¬ G.Adj 0 1) := by tauto have h01 : (¬ G.Adj 0 1) → Gᶜ.Adj (0 : Fin 4) 1 := fun h => (SimpleGraph.compl_adj G 0 1).2 ⟨by decide, h⟩ have h12 : (¬ G.Adj 1 2) → Gᶜ.Adj (1 : Fin 4) 2 := fun h => (SimpleGraph.compl_adj G 1 2).2 ⟨by decide, h⟩ have h23 : (¬ G.Adj 2 3) → Gᶜ.Adj (2 : Fin 4) 3 := fun h => (SimpleGraph.compl_adj G 2 3).2 ⟨by decide, h⟩ have h30 : (¬ G.Adj 3 0) → Gᶜ.Adj (3 : Fin 4) 0 := fun h => (SimpleGraph.compl_adj G 3 0).2 ⟨by decide, h⟩ rcases key with h | h | h | h | h | h · exact Or.inl (op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1 G h.1 h.2) · exact Or.inl (op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0 G ((SimpleGraph.adj_comm G 0 3).2 h.1) h.2) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0 Gᶜ (h01 h.1) (h12 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1 Gᶜ (h12 h.1) (h23 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2 Gᶜ (h23 h.1) (h30 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3 Gᶜ (h30 h.1) (h01 h.2))
For any N < 4, the cyclic Ramsey property fails.
We test the property on the complete graph ⊤ on Fin N. If ⊤ contained a cyclic copy of NM_4, the embedding f : Fin 4 → Fin N would be injective, forcing 4 ≤ N by `Fintype.card_le_of_injective`, which contradicts N < 4. If instead the complement ⊤ᶜ contained a copy of MP_3, the edge {0, 1} would map to an edge in ⊤ᶜ, but ⊤ᶜ has no edges (`SimpleGraph.compl_adj` and `SimpleGraph.top_adj`), giving a contradiction in both branches.
uses
Fintype.card_le_of_injective,SimpleGraph.compl_adj,SimpleGraph.top_adj/-- No `N < 4` has the cyclic Ramsey property: `NM_4` needs `4` vertices, and the complete colouring has no `MP_3` in the empty complement. -/ lemma op_1258_cyclic_ramsey_k2_l3_not_property_of_lt (N : ℕ) (hN : N < 4) : ¬ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N := by intro h rcases h ⊤ with h | h · rcases h with ⟨f, hf, -, -⟩ have h4 : 4 ≤ N := by have := Fintype.card_le_of_injective f hf simpa using this omega · rcases h with ⟨f, hf, hadj, -⟩ have h01 : (monotone_path 3).Adj (0 : Fin 3) 1 := by simp [monotone_path, SimpleGraph.fromRel] have hbad := (SimpleGraph.compl_adj (⊤ : SimpleGraph (Fin N)) (f 0) (f 1)).1 (hadj h01) exact hbad.2 ((SimpleGraph.top_adj (f 0) (f 1)).2 (hf.ne (by decide)))
The cyclic Ramsey number R_cyc(NM_4, MP_3) is equal to 4.
The cyclic Ramsey number is defined as the infimum of all positive integers N satisfying the cyclic Ramsey property. Since N = 4 has the property and 0 < 4, the infimum is at most 4 (`Nat.sInf_le`). The infimum itself must satisfy the property (`Nat.sInf_mem`); if it were strictly less than 4 (`not_le`), that would contradict the fact that no N < 4 has the property. By antisymmetry (`le_antisymm`), the infimum is exactly 4.
uses
op_1258_cyclic_ramsey_k2_l3_property_four,le_antisymm,Nat.sInf_le,Nat.sInf_mem,not_le,op_1258_cyclic_ramsey_k2_l3_not_property_of_lt/-- Smallest even-k instance of Conjecture 4.32: R_cyc(NM_4, MP_3) = 4. -/ theorem op_1258_cyclic_ramsey_k2_l3 : cyclic_ramsey_number (nested_matching 2) (monotone_path 3) = 4 := by have hmem : 4 ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N} := ⟨by norm_num, op_1258_cyclic_ramsey_k2_l3_property_four⟩ refine le_antisymm (Nat.sInf_le hmem) ?_ have hinf := Nat.sInf_mem (⟨4, hmem⟩ : {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N}.Nonempty) by_contra hcon rw [not_le] at hcon exact op_1258_cyclic_ramsey_k2_l3_not_property_of_lt _ hcon hinf.2
decidable_of_iff- A proposition b is decidable if it is logically equivalent to a decidable proposition a.
Iff.rfl- Logical equivalence is reflexive (a ↔ a).
SimpleGraph.fromRel- Constructs a simple graph on a vertex type from a binary relation.
op_1258_cyclic_ramsey_k2_l3_rot4_inj- For every shift j, the rotation map on Fin 4 by j is injective.
op_1258_cyclic_ramsey_k2_l3_rot4_sbtw- For every shift j, rotation by j preserves strict cyclic betweenness on Fin 4.
op_1258_cyclic_ramsey_k2_l3_nm4_cases- The only edges of the nested matching NM_4 are {0, 3} and {1, 2}.
SimpleGraph.adj_comm- Adjacency in any simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u.
op_1258_cyclic_ramsey_k2_l3_rot34_inj- For every shift j, the shifted embedding of Fin 3 into Fin 4 is injective.
op_1258_cyclic_ramsey_k2_l3_rot34_sbtw- For every shift j, the shifted embedding of Fin 3 into Fin 4 preserves strict cyclic betweenness.
op_1258_cyclic_ramsey_k2_l3_mp3_cases- The only edges of the monotone path MP_3 are {0, 1} and {1, 2}.
SimpleGraph.compl_adj- Vertices v and w are adjacent in the complement graph Gᶜ if and only if v ≠ w and they are not adjacent in G.
Or.inl- Left introduction for disjunction: a implies a ∨ b.
Or.inr- Right introduction for disjunction: b implies a ∨ b.
op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1- A graph on Fin 4 containing edges {0, 1} and {2, 3} contains a cyclic copy of NM_4.
op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0- A graph on Fin 4 containing edges {0, 3} and {1, 2} contains a cyclic copy of NM_4.
op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0- A graph on Fin 4 containing edges {0, 1} and {1, 2} contains a cyclic copy of MP_3.
op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1- A graph on Fin 4 containing edges {1, 2} and {2, 3} contains a cyclic copy of MP_3.
op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2- A graph on Fin 4 containing edges {2, 3} and {3, 0} contains a cyclic copy of MP_3.
op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3- A graph on Fin 4 containing edges {3, 0} and {0, 1} contains a cyclic copy of MP_3.
Fintype.card_le_of_injective- An injective map between finite types implies that the cardinality of the domain is at most the cardinality of the codomain.
SimpleGraph.top_adj- In the complete graph ⊤, distinct vertices are adjacent.
op_1258_cyclic_ramsey_k2_l3_property_four- The cyclic Ramsey property holds for NM_4 and MP_3 on 4 vertices.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- The infimum of a set of natural numbers is at most any member of that set.
Nat.sInf_mem- A nonempty set of natural numbers contains its infimum.
not_le- In a linear order, ¬(a ≤ b) is equivalent to b < a.
op_1258_cyclic_ramsey_k2_l3_not_property_of_lt- For any N < 4, the cyclic Ramsey property for NM_4 and MP_3 fails.
- Injectivity and cyclic order preservation of rotations on Fin 4 and Fin 3 are verified mechanically by finite exhaustive evaluation (`decide`). The case split on the four edges of the 4-cycle is discharged by propositional tautology checking (`tauto`).
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.
/-- Decidability of strict betweenness on `Fin n`, through the linear-order instance. -/instance op_1258_cyclic_ramsey_k2_l3_instDecidableSBtwFin {n : ℕ} (a b c : Fin n) : Decidable (sbtw a b c) := decidable_of_iff (a < b ∧ b < c ∨ b < c ∧ c < a ∨ c < a ∧ a < b) Iff.rfl/-- Rotation of the cyclic order on `Fin 4` by `j`. -/def op_1258_cyclic_ramsey_k2_l3_rot4 (j u : Fin 4) : Fin 4 := ⟨(j.val + u.val) % 4, by omega⟩/-- Rotation of `Fin 3` into the cyclic order on `Fin 4` by `j`. -/def op_1258_cyclic_ramsey_k2_l3_rot34 (j : Fin 4) (u : Fin 3) : Fin 4 := ⟨(j.val + u.val) % 4, by omega⟩lemma op_1258_cyclic_ramsey_k2_l3_rot4_inj : ∀ j : Fin 4, Function.Injective (op_1258_cyclic_ramsey_k2_l3_rot4 j) := by decidelemma op_1258_cyclic_ramsey_k2_l3_rot4_sbtw : ∀ (j u v w : Fin 4), sbtw u v w → sbtw (op_1258_cyclic_ramsey_k2_l3_rot4 j u) (op_1258_cyclic_ramsey_k2_l3_rot4 j v) (op_1258_cyclic_ramsey_k2_l3_rot4 j w) := by decidelemma op_1258_cyclic_ramsey_k2_l3_rot34_inj : ∀ j : Fin 4, Function.Injective (op_1258_cyclic_ramsey_k2_l3_rot34 j) := by decidelemma op_1258_cyclic_ramsey_k2_l3_rot34_sbtw : ∀ (j : Fin 4) (u v w : Fin 3), sbtw u v w → sbtw (op_1258_cyclic_ramsey_k2_l3_rot34 j u) (op_1258_cyclic_ramsey_k2_l3_rot34 j v) (op_1258_cyclic_ramsey_k2_l3_rot34 j w) := by decide/-- The edges of `NM_4` are `{0,3}` and `{1,2}`. -/lemma op_1258_cyclic_ramsey_k2_l3_nm4_cases {u v : Fin 4} (h : (nested_matching 2).Adj u v) : (u = 0 ∧ v = 3) ∨ (u = 3 ∧ v = 0) ∨ (u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1) := by fin_cases u <;> fin_cases v <;> simp_all [nested_matching, SimpleGraph.fromRel]/-- The edges of `MP_3` are `{0,1}` and `{1,2}`. -/lemma op_1258_cyclic_ramsey_k2_l3_mp3_cases {u v : Fin 3} (h : (monotone_path 3).Adj u v) : (u = 0 ∧ v = 1) ∨ (u = 1 ∧ v = 0) ∨ (u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1) := by fin_cases u <;> fin_cases v <;> simp_all [monotone_path, SimpleGraph.fromRel]/-- Two nested edges `03` and `12` form a cyclic copy of `NM_4`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0 (G : SimpleGraph (Fin 4)) (h03 : G.Adj 0 3) (h12 : G.Adj 1 2) : cyclic_has_copy (nested_matching 2) G := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot4 0, op_1258_cyclic_ramsey_k2_l3_rot4_inj 0, ?_, op_1258_cyclic_ramsey_k2_l3_rot4_sbtw 0⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_nm4_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h03 · exact (SimpleGraph.adj_comm G 0 3).1 h03 · exact h12 · exact (SimpleGraph.adj_comm G 1 2).1 h12/-- The rotated edges `01` and `23` form a cyclic copy of `NM_4`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1 (G : SimpleGraph (Fin 4)) (h01 : G.Adj 0 1) (h23 : G.Adj 2 3) : cyclic_has_copy (nested_matching 2) G := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot4 1, op_1258_cyclic_ramsey_k2_l3_rot4_inj 1, ?_, op_1258_cyclic_ramsey_k2_l3_rot4_sbtw 1⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_nm4_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact (SimpleGraph.adj_comm G 0 1).1 h01 · exact h01 · exact h23 · exact (SimpleGraph.adj_comm G 2 3).1 h23/-- The cyclic path `0-1-2` in `H` is a copy of `MP_3`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0 (H : SimpleGraph (Fin 4)) (h01 : H.Adj 0 1) (h12 : H.Adj 1 2) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 0, op_1258_cyclic_ramsey_k2_l3_rot34_inj 0, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 0⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h01 · exact (SimpleGraph.adj_comm H 0 1).1 h01 · exact h12 · exact (SimpleGraph.adj_comm H 1 2).1 h12/-- The cyclic path `1-2-3` in `H` is a copy of `MP_3`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1 (H : SimpleGraph (Fin 4)) (h12 : H.Adj 1 2) (h23 : H.Adj 2 3) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 1, op_1258_cyclic_ramsey_k2_l3_rot34_inj 1, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 1⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h12 · exact (SimpleGraph.adj_comm H 1 2).1 h12 · exact h23 · exact (SimpleGraph.adj_comm H 2 3).1 h23/-- The cyclic path `2-3-0` in `H` is a copy of `MP_3`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2 (H : SimpleGraph (Fin 4)) (h23 : H.Adj 2 3) (h30 : H.Adj 3 0) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 2, op_1258_cyclic_ramsey_k2_l3_rot34_inj 2, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 2⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h23 · exact (SimpleGraph.adj_comm H 2 3).1 h23 · exact h30 · exact (SimpleGraph.adj_comm H 3 0).1 h30/-- The cyclic path `3-0-1` in `H` is a copy of `MP_3`. -/lemma op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3 (H : SimpleGraph (Fin 4)) (h30 : H.Adj 3 0) (h01 : H.Adj 0 1) : cyclic_has_copy (monotone_path 3) H := by refine ⟨op_1258_cyclic_ramsey_k2_l3_rot34 3, op_1258_cyclic_ramsey_k2_l3_rot34_inj 3, ?_, op_1258_cyclic_ramsey_k2_l3_rot34_sbtw 3⟩ intro u v huv rcases op_1258_cyclic_ramsey_k2_l3_mp3_cases huv with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h30 · exact (SimpleGraph.adj_comm H 3 0).1 h30 · exact h01 · exact (SimpleGraph.adj_comm H 0 1).1 h01/-- Every `2`-colouring of the cyclically ordered `K_4` contains a monochromatic copy of `NM_4`or of `MP_3`: a propositional case analysis on the four edges of the `4`-cycle. -/lemma op_1258_cyclic_ramsey_k2_l3_property_four : cyclic_ramsey_property (nested_matching 2) (monotone_path 3) 4 := by intro G have key : (G.Adj 0 1 ∧ G.Adj 2 3) ∨ (G.Adj 3 0 ∧ G.Adj 1 2) ∨ (¬ G.Adj 0 1 ∧ ¬ G.Adj 1 2) ∨ (¬ G.Adj 1 2 ∧ ¬ G.Adj 2 3) ∨ (¬ G.Adj 2 3 ∧ ¬ G.Adj 3 0) ∨ (¬ G.Adj 3 0 ∧ ¬ G.Adj 0 1) := by tauto have h01 : (¬ G.Adj 0 1) → Gᶜ.Adj (0 : Fin 4) 1 := fun h => (SimpleGraph.compl_adj G 0 1).2 ⟨by decide, h⟩ have h12 : (¬ G.Adj 1 2) → Gᶜ.Adj (1 : Fin 4) 2 := fun h => (SimpleGraph.compl_adj G 1 2).2 ⟨by decide, h⟩ have h23 : (¬ G.Adj 2 3) → Gᶜ.Adj (2 : Fin 4) 3 := fun h => (SimpleGraph.compl_adj G 2 3).2 ⟨by decide, h⟩ have h30 : (¬ G.Adj 3 0) → Gᶜ.Adj (3 : Fin 4) 0 := fun h => (SimpleGraph.compl_adj G 3 0).2 ⟨by decide, h⟩ rcases key with h | h | h | h | h | h · exact Or.inl (op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot1 G h.1 h.2) · exact Or.inl (op_1258_cyclic_ramsey_k2_l3_copy_nm4_rot0 G ((SimpleGraph.adj_comm G 0 3).2 h.1) h.2) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot0 Gᶜ (h01 h.1) (h12 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot1 Gᶜ (h12 h.1) (h23 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot2 Gᶜ (h23 h.1) (h30 h.2)) · exact Or.inr (op_1258_cyclic_ramsey_k2_l3_copy_mp3_rot3 Gᶜ (h30 h.1) (h01 h.2))/-- No `N < 4` has the cyclic Ramsey property: `NM_4` needs `4` vertices, and the completecolouring has no `MP_3` in the empty complement. -/lemma op_1258_cyclic_ramsey_k2_l3_not_property_of_lt (N : ℕ) (hN : N < 4) : ¬ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N := by intro h rcases h ⊤ with h | h · rcases h with ⟨f, hf, -, -⟩ have h4 : 4 ≤ N := by have := Fintype.card_le_of_injective f hf simpa using this omega · rcases h with ⟨f, hf, hadj, -⟩ have h01 : (monotone_path 3).Adj (0 : Fin 3) 1 := by simp [monotone_path, SimpleGraph.fromRel] have hbad := (SimpleGraph.compl_adj (⊤ : SimpleGraph (Fin N)) (f 0) (f 1)).1 (hadj h01) exact hbad.2 ((SimpleGraph.top_adj (f 0) (f 1)).2 (hf.ne (by decide)))/-- Smallest even-k instance of Conjecture 4.32: R_cyc(NM_4, MP_3) = 4. -/theorem op_1258_cyclic_ramsey_k2_l3 : cyclic_ramsey_number (nested_matching 2) (monotone_path 3) = 4 := by have hmem : 4 ∈ {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N} := ⟨by norm_num, op_1258_cyclic_ramsey_k2_l3_property_four⟩ refine le_antisymm (Nat.sInf_le hmem) ?_ have hinf := Nat.sInf_mem (⟨4, hmem⟩ : {N : ℕ | 0 < N ∧ cyclic_ramsey_property (nested_matching 2) (monotone_path 3) N}.Nonempty) by_contra hcon rw [not_le] at hcon exact op_1258_cyclic_ramsey_k2_l3_not_property_of_lt _ hcon hinf.2