AFTD Auto-Formalizing Theoretical Domains

ordered_ramsey_monotone_cycle_alternating_path_two

theoremverified

For all integers k ≥ 3, the ordered Ramsey number of the monotone cycle MC_k and the alternating path AP_2 is equal to k.

Statement

theorem ordered_ramsey_monotone_cycle_alternating_path_two
    (k : ℕ) (hk : 3 ≤ k) :
    ordered_ramsey_number (monotone_cycle k) (alternating_path 2) = k
Source
arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 5
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • ordered_ramsey_numberThe ordered Ramsey number R_ord(H, H') of ordered graphs H and H' is the infimum of natural numbers N such that every 2-edge-colouring of…
  • monotone_cycleThe monotone cycle MC_k is the ordered simple graph on Fin k with edges {i, i+1} for 0 ≤ i < k-1 and the edge {0, k-1}.
  • alternating_pathThe alternating path AP_n is the ordered simple graph on Fin n whose edges connect consecutive vertices in the alternating sequence 0,…
  • ordered_ramsey_propFor ordered graphs H and H' and natural number N, ordered_ramsey_prop H H' N holds if for every graph G on Fin N, G contains an ordered…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • has_ordered_copyAn ordered graph G contains an ordered copy of an ordered graph H if there exists a strictly monotone map f from the vertex set of H to…
  • alternating_path_vertexThe m-th vertex in the alternating path AP_n is m/2 if m is even, and n - 1 - m/2 if m is odd.
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…

Read back from the Lean

For every natural number $k$ such that $k \ge 3$, the ordered Ramsey number of the monotone cycle of length $k$ (on vertex set Fin k) and the alternating path of length 1 (on vertex set Fin 2) is equal to $k$.

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 ordered Ramsey number r_<(MC_k, AP_2) is the minimum number of vertices N such that every 2-coloring of the complete ordered graph on N vertices contains either an ordered MC_k in the first color or an ordered AP_2 in the second. First, AP_2 has only two vertices and one edge, making it identical to K_2. On k vertices, if the first color is K_k it trivially contains MC_k; otherwise any missing edge yields an ordered K_2 in the second color, giving the upper bound k. On M < k vertices, taking the first color to be K_M leaves no edges for the second color while lacking enough vertices to embed MC_k, establishing the matching lower bound.

  1. The alternating path on 2 vertices is the complete graph on 2 vertices (AP_2 = ⊤).

    Unfolding the definition of alternating_path 2 via SimpleGraph.fromRel, two vertices in Fin 2 are adjacent if and only if they are distinct. Exhaustive case checking over all pairs of vertices in Fin 2 shows this matches the adjacency relation of the complete graph ⊤.

    lines 5–10

    uses SimpleGraph.fromRel

      have _ := hk
      open SimpleGraph in
      have halt : alternating_path 2 = ⊤ := by
        ext a b
        simp [alternating_path, SimpleGraph.fromRel, alternating_path_vertex]
        fin_cases a <;> fin_cases b <;> decide
  2. If G is the complete graph on k vertices, then G contains an ordered copy of the monotone cycle MC_k.

    To show the upper bound ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) k, let G be a graph on Fin k. In the case G = ⊤, the identity map id is strictly monotone (strictMono_id) and sends adjacent vertices of MC_k (which are distinct) to adjacent vertices of ⊤ by SimpleGraph.top_adj.

    lines 11–20

    uses strictMono_id, SimpleGraph.top_adj

      have hupper : ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) k := by
        intro G
        by_cases h : G = ⊤
        · left
          subst h
          use id
          refine ⟨strictMono_id, ?_⟩
          intro u v huv
          rw [SimpleGraph.top_adj]
          exact huv.ne
  3. If G is not the complete graph on k vertices, then there exists a pair of vertices u < v that are not adjacent in G.

    Assuming for contradiction that every pair u < v is adjacent in G, then by trichotomy of the linear order (lt_trichotomy) and symmetry of adjacency, every pair of distinct vertices is adjacent in G. By SimpleGraph.top_adj, G would equal ⊤, contradicting G ≠ ⊤.

    lines 21–36

    uses SimpleGraph.top_adj, lt_trichotomy

        · right
          have hne : ∃ u v : Fin k, u < v ∧ ¬ G.Adj u v := by
            by_contra! hall
            apply h
            ext u v
            constructor
            · intro huv
              rw [SimpleGraph.top_adj]
              exact huv.ne
            · intro huv
              rw [SimpleGraph.top_adj] at huv
              rcases lt_trichotomy u v with hlt | heq | hgt
              · exact hall u v hlt
              · exfalso; exact huv heq
              · rw [G.adj_comm]
                exact hall v u hgt
  4. If G is not the complete graph, its complement Gᶜ contains an ordered copy of AP_2, completing the upper bound.

    Given a non-adjacent pair u < v in G, define f : Fin 2 → Fin k by f(0) = u and f(1) = v. Since u < v and < is irreflexive (lt_irrefl), f is strictly monotone. The only edge of AP_2 = ⊤ is between 0 and 1 (SimpleGraph.top_adj), which maps to the non-edge {u, v} of G, hence an edge in Gᶜ by SimpleGraph.compl_adj. Thus f is an ordered embedding of AP_2 into Gᶜ.

    lines 37–66

    uses lt_irrefl, SimpleGraph.top_adj, SimpleGraph.compl_adj

          rcases hne with ⟨u, v, hlt, hnotadj⟩
          let f : Fin 2 → Fin k := fun x => if x = 0 then u else v
          use f
          constructor
          · intro x y hxy
            fin_cases x <;> fin_cases y
            · exfalso; exact lt_irrefl _ hxy
            · dsimp [f]
              exact hlt
            · exfalso; revert hxy; decide
            · exfalso; exact lt_irrefl _ hxy
          · intro x y hxy
            rw [halt, SimpleGraph.top_adj] at hxy
            rw [SimpleGraph.compl_adj]
            constructor
            · fin_cases x <;> fin_cases y
              · exfalso; exact hxy rfl
              · dsimp [f]
                exact hlt.ne
              · dsimp [f]
                exact hlt.ne'
              · exfalso; exact hxy rfl
            · fin_cases x <;> fin_cases y
              · exfalso; exact hxy rfl
              · dsimp [f]
                exact hnotadj
              · dsimp [f]
                rw [G.adj_comm]
                exact hnotadj
              · exfalso; exact hxy rfl
  5. For any M < k, the ordered Ramsey property fails for M.

    Consider the complete graph G = ⊤ on Fin M. If ⊤ contained an ordered copy of MC_k, the embedding f : Fin k → Fin M would be injective, implying k ≤ M by Fintype.card_le_of_injective and Fintype.card_fin, contradicting M < k. If ⊤ᶜ contained an ordered copy of AP_2, the edge between 0 and 1 in AP_2 (SimpleGraph.top_adj) would have to map to an edge in ⊤ᶜ, but ⊤ᶜ = ⊥ by compl_top has no edges, which is impossible.

    lines 67–80

    uses Fintype.card_le_of_injective, Fintype.card_fin, SimpleGraph.top_adj, compl_top

      have hlower : ∀ M < k, ¬ ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) M := by
        intro M hM hprop
        have h := hprop ⊤
        rcases h with ⟨f, hf_mono, hf_adj⟩ | ⟨g, hg_mono, hg_adj⟩
        · have hinj : Function.Injective f := hf_mono.injective
          have hle := Fintype.card_le_of_injective f hinj
          simp only [Fintype.card_fin] at hle
          omega
        · have h01 : (alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by
            rw [halt, SimpleGraph.top_adj]
            decide
          have hadj := hg_adj h01
          simp only [compl_top] at hadj
          exact hadj
  6. The ordered Ramsey number of MC_k and AP_2 equals k.

    The ordered Ramsey number is defined as the infimum of all integers satisfying the Ramsey property. The set of such integers is nonempty because k satisfies the property (hupper). By csInf_eq_iff, the infimum is k because k belongs to the set and any M in the set must satisfy k ≤ M (as any M < k fails the property by hlower).

    lines 81–88

    uses csInf_eq_iff

      dsimp [ordered_ramsey_number]
      have hnonempty : (Set.Nonempty {n | ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) n}) :=
        ⟨k, hupper⟩
      rw [csInf_eq_iff hnonempty]
      refine ⟨hupper, ?_⟩
      intro M hM
      by_contra! hlt
      exact hlower M hlt hM
SimpleGraph.fromRel
constructs a simple graph from a binary relation by symmetrizing it and removing self-loops
strictMono_id
the identity function is strictly monotone
SimpleGraph.top_adj
two vertices in the complete graph are adjacent if and only if they are distinct
lt_trichotomy
for any two elements in a linear order, either the first is less than the second, they are equal, or the second is less than the first
lt_irrefl
the strict order relation < is irreflexive (no element is strictly less than itself)
SimpleGraph.compl_adj
two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph
Fintype.card_le_of_injective
if there is an injective function between finite types, the cardinality of the domain is at most the cardinality of the codomain
Fintype.card_fin
the cardinality of Fin n is n
compl_top
the complement of the top element (the complete graph) is the bottom element (the empty graph)
csInf_eq_iff
for a nonempty set in a conditionally complete well-founded linear order, the infimum is n if and only if n is in the set and bounds it from below

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

/-- The ordered Ramsey number of the monotone cycle MC_k versus the alternating path AP_2 is k for all k ≥ 3. -/theorem ordered_ramsey_monotone_cycle_alternating_path_two    (k : ℕ) (hk : 3 ≤ k) :    ordered_ramsey_number (monotone_cycle k) (alternating_path 2) = k := by  have _ := hk  open SimpleGraph in  have halt : alternating_path 2 = ⊤ := by    ext a b    simp [alternating_path, SimpleGraph.fromRel, alternating_path_vertex]    fin_cases a <;> fin_cases b <;> decide  have hupper : ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) k := by    intro G    by_cases h : G = ⊤    · left      subst h      use id      refine ⟨strictMono_id, ?_⟩      intro u v huv      rw [SimpleGraph.top_adj]      exact huv.ne    · right      have hne : ∃ u v : Fin k, u < v ∧ ¬ G.Adj u v := by        by_contra! hall        apply h        ext u v        constructor        · intro huv          rw [SimpleGraph.top_adj]          exact huv.ne        · intro huv          rw [SimpleGraph.top_adj] at huv          rcases lt_trichotomy u v with hlt | heq | hgt          · exact hall u v hlt          · exfalso; exact huv heq          · rw [G.adj_comm]            exact hall v u hgt      rcases hne with ⟨u, v, hlt, hnotadj⟩      let f : Fin 2 → Fin k := fun x => if x = 0 then u else v      use f      constructor      · intro x y hxy        fin_cases x <;> fin_cases y        · exfalso; exact lt_irrefl _ hxy        · dsimp [f]          exact hlt        · exfalso; revert hxy; decide        · exfalso; exact lt_irrefl _ hxy      · intro x y hxy        rw [halt, SimpleGraph.top_adj] at hxy        rw [SimpleGraph.compl_adj]        constructor        · fin_cases x <;> fin_cases y          · exfalso; exact hxy rfl          · dsimp [f]            exact hlt.ne          · dsimp [f]            exact hlt.ne'          · exfalso; exact hxy rfl        · fin_cases x <;> fin_cases y          · exfalso; exact hxy rfl          · dsimp [f]            exact hnotadj          · dsimp [f]            rw [G.adj_comm]            exact hnotadj          · exfalso; exact hxy rfl  have hlower : ∀ M < k, ¬ ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) M := by    intro M hM hprop    have h := hprop ⊤    rcases h with ⟨f, hf_mono, hf_adj⟩ | ⟨g, hg_mono, hg_adj⟩    · have hinj : Function.Injective f := hf_mono.injective      have hle := Fintype.card_le_of_injective f hinj      simp only [Fintype.card_fin] at hle      omega    · have h01 : (alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by        rw [halt, SimpleGraph.top_adj]        decide      have hadj := hg_adj h01      simp only [compl_top] at hadj      exact hadj  dsimp [ordered_ramsey_number]  have hnonempty : (Set.Nonempty {n | ordered_ramsey_prop (monotone_cycle k) (alternating_path 2) n}) :=    ⟨k, hupper⟩  rw [csInf_eq_iff hnonempty]  refine ⟨hupper, ?_⟩  intro M hM  by_contra! hlt  exact hlower M hlt hM
See it in the graphDiscuss this resultChallenge it