AFTD Auto-Formalizing Theoretical Domains

op_1258_cyclic_ramsey_k_one

theoremverifiedformalization

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.

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

    lines 6–7

    uses Fintype.card_le_of_injective

      obtain ⟨f, hf, _⟩ := h
      simpa using Fintype.card_le_of_injective f hf
  2. 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.

    lines 12–16

    uses SimpleGraph.bot_adj

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

    lines 21–30

    uses sbtw_iff

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

    lines 35–40

    uses Fin.castLE_injective, SimpleGraph.top_adj, sbtw_iff, Fin.lt_def, Fin.val_castLE

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

    lines 46–50

    uses op_1258_cyclic_ramsey_k_one_edge_copy

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

    lines 51–59

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

    lines 64–71

    uses op_1258_cyclic_ramsey_k_one_not_copy_bot, op_1258_cyclic_ramsey_k_one_vertex_bound

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

    lines 76–79

    uses op_1258_cyclic_ramsey_k_one_property, Nat.sInf_le, le_antisymm

      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) ?_
  9. 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.

    lines 80–85

    uses not_le, Nat.sInf_mem, op_1258_cyclic_ramsey_k_one_not_property

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

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