AFTD Auto-Formalizing Theoretical Domains

op_1258_cyclic_ramsey_k2_l3

theoremverifiedformalization

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.

  1. 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`).

    lines 1–11

    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⟩
    
  2. 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`).

    lines 12–25

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

    lines 26–35

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

    lines 36–59

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

    lines 60–107

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

    lines 108–131

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

    lines 132–148

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

    lines 149–159

    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.

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

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