AFTD Auto-Formalizing Theoretical Domains

ordered_ramsey_monotone_cycle_three_alternating_path_three

theoremverified

The ordered Ramsey number of the monotone cycle MC_3 and the alternating path AP_3 is equal to 5.

Statement

theorem ordered_ramsey_monotone_cycle_three_alternating_path_three :
    ordered_ramsey_number (monotone_cycle 3) (alternating_path 3) = 5
Source
arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 5
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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,…
  • 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.
  • 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.

Read back from the Lean

The ordered Ramsey number of the monotone cycle on 3 vertices and the alternating path on 3 vertices is equal to 5. More precisely, 5 is the least natural number $N$ (under sInf on $\mathbb{N}$) such that for every simple graph $G$ on the vertex set Fin N, either: 1. There exists a strictly monotone map $f : \text{Fin } 3 \to \text{Fin } N$ such that for all vertices $u, v \in \text{Fin } 3$, if $u$ and $v$ are adjacent in monotone_cycle 3, then $f(u)$ and $f(v)$ are adjacent in $G$; or 2. There exists a strictly monotone map $g : \text{Fin } 3 \to \text{Fin } N$ such that for all vertices $u, v \in \text{Fin } 3$, if $u$ and $v$ are adjacent in alternating_path 3, then $g(u)$ and $g(v)$ are adjacent in the complement graph $G^c$.

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 proof determines that the ordered Ramsey number R_<(MC_3, AP_3) = 5 by establishing matching upper and lower bounds. For the upper bound N = 5, any graph G on 5 ordered vertices either contains an ordered alternating path AP_3 in its complement Gᶜ or avoids two non-edges from any lower pair to a higher vertex; a propositional case exhaustion then forces G to contain a monochromatic monotone triangle MC_3. For the lower bound, an explicit 4-vertex graph G_4 with edges {0, 2}, {0, 3}, {1, 3} is shown to contain no ordered MC_3 while its complement contains no ordered AP_3, which extends to all M < 5 by monotonicity.

  1. The ordered Ramsey property is monotone in the number of vertices: if it holds for M, it holds for any N ≥ M.

    Given an N-vertex graph G, embed Fin M into Fin N via the order-preserving identity inclusion. Pull G back to an M-vertex graph G'. Applying the hypothesis to G' yields an ordered copy of H in G' or an ordered copy of H' in G'ᶜ; composing the embedding with the inclusion maps that copy strictly monotonically into G or Gᶜ.

    lines 6–24

    uses compl_adj

      intro G
      let emb : Fin M → Fin N := fun x => ⟨x.val, by omega⟩
      have hemb_mono : StrictMono emb := fun _ _ hxy => hxy
      have hemb_inj : Function.Injective emb := hemb_mono.injective
      let G' : SimpleGraph (Fin M) :=
        { Adj := fun u v => G.Adj (emb u) (emb v)
          symm := ⟨fun {_ _} h => G.adj_symm h⟩
          loopless := ⟨fun _ h => G.irrefl h⟩ }
      rcases hM G' with ⟨f, hf_mono, hf_adj⟩ | ⟨f, hf_mono, hf_adj⟩
      · left
        refine ⟨emb ∘ f, hemb_mono.comp hf_mono, ?_⟩
        intro u v huv
        exact hf_adj huv
      · right
        refine ⟨emb ∘ f, hemb_mono.comp hf_mono, ?_⟩
        intro u v huv
        have := hf_adj huv
        rw [compl_adj] at this ⊢
        refine ⟨fun h => this.1 (hemb_inj h), this.2⟩
  2. An existential condition over indices m such that m + 1 < 3 simplifies to the disjunction P(0) ∨ P(1).

    Since m is a natural number with m + 1 < 3, the only possibilities are m = 0 and m = 1.

    lines 28–36

      constructor
      · rintro ⟨m, hm, hp⟩
        have : m = 0 ∨ m = 1 := by omega
        rcases this with rfl | rfl
        · left; exact hp
        · right; exact hp
      · rintro (h0 | h1)
        · exact ⟨0, by decide, h0⟩
        · exact ⟨1, by decide, h1⟩
  3. The monotone cycle MC_3 is the complete graph ⊤ on Fin 3. automation

    Unfolding the definition of monotone_cycle on 3 vertices yields all distinct pairs {0, 1}, {1, 2}, and {0, 2}, which is exhaustively verified for all pairs of vertices in Fin 3.

    lines 39–41

    uses SimpleGraph.fromRel_adj

      ext a b
      simp [monotone_cycle, SimpleGraph.fromRel_adj]
      fin_cases a <;> fin_cases b <;> decide
  4. The edges of the alternating path AP_3 on Fin 3 are precisely the pairs {0, 2} and {1, 2}. automation

    By unfolding the alternating path definition, using the simplified existential quantifier, and checking all pairs in Fin 3, the only adjacent pairs are {0, 2} and {1, 2}.

    lines 46–47

    uses fromRel_adj, ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_three

      simp only [alternating_path, fromRel_adj, ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_three, alternating_path_vertex]
      fin_cases a <;> fin_cases b <;> decide
  5. Any three mutually adjacent vertices u < v < w in G contain an ordered copy of MC_3.

    Define f : Fin 3 → Fin N by mapping 0, 1, 2 to u, v, w. This map is strictly monotone since u < v < w. Because MC_3 is the complete graph ⊤, every pair of distinct vertices in Fin 3 is an edge, and their images under f are pairs from {u, v, w}, which are all edges of G by hypothesis.

    lines 52–77

    uses lt_irrefl, ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj

      let f : Fin 3 → Fin N := fun x =>
        if x = 0 then u else if x = 1 then v else w
      refine ⟨f, ?_, ?_⟩
      · intro x y hxy
        fin_cases x <;> fin_cases y
        · exfalso; exact lt_irrefl _ hxy
        · dsimp [f]; exact huv
        · dsimp [f]; exact huv.trans hvw
        · exfalso; revert hxy; decide
        · exfalso; exact lt_irrefl _ hxy
        · dsimp [f]; exact hvw
        · exfalso; revert hxy; decide
        · exfalso; revert hxy; decide
        · exfalso; exact lt_irrefl _ hxy
      · intro x y hxy
        rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj] at hxy
        fin_cases x <;> fin_cases y
        · exfalso; exact hxy rfl
        · dsimp [f]; exact hadj1
        · dsimp [f]; exact hadj3
        · dsimp [f]; exact hadj1.symm
        · exfalso; exact hxy rfl
        · dsimp [f]; exact hadj2
        · dsimp [f]; exact hadj3.symm
        · dsimp [f]; exact hadj2.symm
        · exfalso; exact hxy rfl
  6. If u < v < w are ordered vertices in G such that neither uw nor vw is an edge of G, then Gᶜ contains an ordered copy of AP_3.

    Define f : Fin 3 → Fin N by sending 0, 1, 2 to u, v, w. The map is strictly monotone. The edges of AP_3 are {0, 2} and {1, 2}, which map to {u, w} and {v, w}. Because neither pair is an edge in G, both are edges in Gᶜ.

    lines 82–108

    uses lt_irrefl, ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj, compl_adj

      let f : Fin 3 → Fin N := fun x =>
        if x = 0 then u else if x = 1 then v else w
      refine ⟨f, ?_, ?_⟩
      · intro x y hxy
        fin_cases x <;> fin_cases y
        · exfalso; exact lt_irrefl _ hxy
        · dsimp [f]; exact huv
        · dsimp [f]; exact huv.trans hvw
        · exfalso; revert hxy; decide
        · exfalso; exact lt_irrefl _ hxy
        · dsimp [f]; exact hvw
        · exfalso; revert hxy; decide
        · exfalso; revert hxy; decide
        · exfalso; exact lt_irrefl _ hxy
      · intro x y hxy
        rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj] at hxy
        rw [compl_adj]
        fin_cases x <;> fin_cases y
        · exfalso; revert hxy; decide
        · exfalso; revert hxy; decide
        · dsimp [f]; exact ⟨(huv.trans hvw).ne, hnot1⟩
        · exfalso; revert hxy; decide
        · exfalso; revert hxy; decide
        · dsimp [f]; exact ⟨hvw.ne, hnot2⟩
        · dsimp [f]; exact ⟨(huv.trans hvw).ne', fun h => hnot1 (G.adj_symm h)⟩
        · dsimp [f]; exact ⟨hvw.ne', fun h => hnot2 (G.adj_symm h)⟩
        · exfalso; revert hxy; decide
  7. Under the AP_3-avoiding conditions on 5 vertices, at least one of the 5 candidate triangles has all three edges present.

    We perform a case analysis on edge e34, then e24, and e23. In each branch, the disjunctions e_{ik} ∨ e_{jk} force other edges until one of the five candidate triangles ({0, 2, 4}, {1, 2, 4}, {0, 3, 4}, {1, 3, 4}, or {2, 3, 4}) is fully present.

    lines 127–146

      by_cases h34 : e34
      · by_cases h24 : e24
        · by_cases h23 : e23
          · right; right; right; right; exact ⟨h23, h34, h24⟩
          · have he03 : e03 := by rcases h023 with h | h; exact h; contradiction
            have he13 : e13 := by rcases h123 with h | h; exact h; contradiction
            rcases h014 with he04 | he14
            · right; right; left; exact ⟨he03, h34, he04⟩
            · right; right; right; left; exact ⟨he13, h34, he14⟩
        · have he04 : e04 := by rcases h024 with h | h; exact h; contradiction
          have he14 : e14 := by rcases h124 with h | h; exact h; contradiction
          rcases h013 with he03 | he13
          · right; right; left; exact ⟨he03, h34, he04⟩
          · right; right; right; left; exact ⟨he13, h34, he14⟩
      · have he04 : e04 := by rcases h034 with h | h; exact h; contradiction
        have he14 : e14 := by rcases h134 with h | h; exact h; contradiction
        have he24 : e24 := by rcases h234 with h | h; exact h; contradiction
        rcases h012 with he02 | he12
        · left; exact ⟨he02, he24, he04⟩
        · right; left; exact ⟨he12, he24, he14⟩
  8. The ordered Ramsey property holds on 5 vertices: every 2-coloring on Fin 5 contains an ordered MC_3 or an ordered AP_3 in the complement.

    Given G on Fin 5, if Gᶜ contains an ordered copy of AP_3, we are done. Otherwise, for every triple u < v < w, at least one of uw or vw must be an edge in G. Applying the propositional case analysis lemma to these edge conditions yields a monochromatic triangle u < v < w in G, which gives an ordered copy of MC_3.

    lines 150–176

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_has_ap3_compl, ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_fast, ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3

      intro G
      by_cases h_ap : has_ordered_copy Gᶜ (alternating_path 3)
      · right; exact h_ap
      · left
        have H_ap : ∀ ⦃u v w : Fin 5⦄, u < v → v < w → G.Adj u w ∨ G.Adj v w := by
          intro u v w huv hvw
          by_contra! h
          exact h_ap (ordered_ramsey_monotone_cycle_three_alternating_path_three_has_ap3_compl G huv hvw h.1 h.2)
        have h_tri := ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_fast
          (G.Adj 0 2) (G.Adj 1 2) (G.Adj 0 3) (G.Adj 1 3) (G.Adj 2 3)
          (G.Adj 0 4) (G.Adj 1 4) (G.Adj 2 4) (G.Adj 3 4)
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
          (H_ap (by decide) (by decide))
        rcases h_tri with ⟨h02, h24, h04⟩ | ⟨h12, h24, h14⟩ | ⟨h03, h34, h04⟩ | ⟨h13, h34, h14⟩ | ⟨h23, h34, h24⟩
        · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h02 h24 h04
        · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h12 h24 h14
        · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h03 h34 h04
        · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h13 h34 h14
        · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h23 h34 h24
  9. The 4-vertex graph G_4 with edges {0, 2}, {0, 3}, {1, 3} is well-defined as a simple graph.

    The definition specifies the adjacency relation explicitly, and tactics verify symmetry by case matching and looplessness by showing u ≠ v for each edge.

    lines 182–193

      symm := ⟨by
        intro u v h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩
        · right; left; exact ⟨h2, h1⟩
        · left; exact ⟨h2, h1⟩
        · right; right; right; left; exact ⟨h2, h1⟩
        · right; right; left; exact ⟨h2, h1⟩
        · right; right; right; right; right; exact ⟨h2, h1⟩
        · right; right; right; right; left; exact ⟨h2, h1⟩⟩
      loopless := ⟨by
        intro u h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega⟩
  10. Every strictly monotone map from Fin 3 to Fin 4 has image {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, or {1, 2, 3}. automation

    Strict monotonicity requires f(0) < f(1) < f(2) in {0, 1, 2, 3}; exhaustive checking over all choices of values shows these four are the only possible images.

    lines 196–205

        (f 0 = 0 ∧ f 1 = 1 ∧ f 2 = 2) ∨
        (f 0 = 0 ∧ f 1 = 1 ∧ f 2 = 3) ∨
        (f 0 = 0 ∧ f 1 = 2 ∧ f 2 = 3) ∨
        (f 0 = 1 ∧ f 1 = 2 ∧ f 2 = 3) := by
      have h01 := hf (by decide : (0 : Fin 3) < 1)
      have h12 := hf (by decide : (1 : Fin 3) < 2)
      generalize ha : f 0 = a at h01 ⊢
      generalize hb : f 1 = b at h01 h12 ⊢
      generalize hc : f 2 = c at h12 ⊢
      fin_cases a <;> fin_cases b <;> fin_cases c <;> omega
  11. G_4 contains no ordered copy of MC_3.

    An ordered copy of MC_3 requires a 3-clique under an increasing map. By checking each of the 4 possible increasing maps, each triple contains a missing edge in G_4: {0, 1} is missing from {0, 1, 2} and {0, 1, 3}, {2, 3} is missing from {0, 2, 3}, and {1, 2} is missing from {1, 2, 3}.

    lines 208–228

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases, ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj

        ¬ has_ordered_copy ordered_ramsey_monotone_cycle_three_alternating_path_three_G4 (monotone_cycle 3) := by
      intro ⟨f, hf_mono, hf_adj⟩
      have h_cases := ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases f hf_mono
      have htop : ∀ ⦃u v : Fin 3⦄, u ≠ v → ordered_ramsey_monotone_cycle_three_alternating_path_three_G4.Adj (f u) (f v) := by
        intro u v huv
        apply hf_adj
        rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj]
        exact huv
      rcases h_cases with ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩
      · have h := htop (by decide : (0 : Fin 3) ≠ 1)
        rw [h0, h1] at h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
      · have h := htop (by decide : (0 : Fin 3) ≠ 1)
        rw [h0, h1] at h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
      · have h := htop (by decide : (1 : Fin 3) ≠ 2)
        rw [h1, h2] at h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
      · have h := htop (by decide : (0 : Fin 3) ≠ 1)
        rw [h0, h1] at h
        rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
  12. G_4ᶜ contains no ordered copy of AP_3.

    In AP_3, {0, 2} is an edge, so an ordered copy in G_4ᶜ requires {f(0), f(2)} to not be an edge of G_4. But for all 4 monotone injections f, the pair {f(0), f(2)} is an edge of G_4 ({0, 2}, {0, 3}, {0, 3}, and {1, 3} respectively), a contradiction.

    lines 231–258

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases, compl_adj, ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj

        ¬ has_ordered_copy ordered_ramsey_monotone_cycle_three_alternating_path_three_G4ᶜ (alternating_path 3) := by
      intro ⟨f, hf_mono, hf_adj⟩
      have h_cases := ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases f hf_mono
      have hap : ∀ ⦃u v : Fin 3⦄, (alternating_path 3).Adj u v → ¬ ordered_ramsey_monotone_cycle_three_alternating_path_three_G4.Adj (f u) (f v) := by
        intro u v huv
        have := hf_adj huv
        rw [compl_adj] at this
        exact this.2
      have h02 : (alternating_path 3).Adj 0 2 := by
        rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj]
        decide
      rcases h_cases with ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩
      · have h := hap h02
        rw [h0, h2] at h
        apply h
        left; decide
      · have h := hap h02
        rw [h0, h2] at h
        apply h
        right; right; left; decide
      · have h := hap h02
        rw [h0, h2] at h
        apply h
        right; right; left; decide
      · have h := hap h02
        rw [h0, h2] at h
        apply h
        right; right; right; right; left; decide
  13. The ordered Ramsey property for MC_3 and AP_3 fails on 4 vertices.

    The graph G_4 witnesses the failure, as it contains neither an ordered MC_3 nor an ordered AP_3 in its complement.

    lines 261–265

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_mc3, ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_ap3

        ¬ ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) 4 := by
      intro hprop
      rcases hprop ordered_ramsey_monotone_cycle_three_alternating_path_three_G4 with h | h
      · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_mc3 h
      · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_ap3 h
  14. For all M < 5, the ordered Ramsey property for MC_3 and AP_3 fails on M vertices.

    If the property held for some M < 5, then since M ≤ 4, monotonicity would imply it holds on 4 vertices, contradicting the 4-vertex counterexample.

    lines 268–272

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_mono, ordered_ramsey_monotone_cycle_three_alternating_path_three_not_prop_four

        ¬ ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) M := by
      intro hprop
      have h4 : ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) 4 :=
        ordered_ramsey_monotone_cycle_three_alternating_path_three_mono _ _ (by omega) hprop
      exact ordered_ramsey_monotone_cycle_three_alternating_path_three_not_prop_four h4
  15. The ordered Ramsey number of MC_3 and AP_3 equals 5.

    The ordered Ramsey number is defined as the infimum of all N for which the ordered Ramsey property holds. Because 5 satisfies the property and no M < 5 satisfies it, 5 is the least element and therefore the infimum.

    lines 276–286

    uses ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_five, ordered_ramsey_monotone_cycle_three_alternating_path_three_forall_lt_not_prop, csInf_eq_iff

        ordered_ramsey_number (monotone_cycle 3) (alternating_path 3) = 5 := by
      have hupper := ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_five
      have hlower := ordered_ramsey_monotone_cycle_three_alternating_path_three_forall_lt_not_prop
      dsimp [ordered_ramsey_number]
      have hnonempty : (Set.Nonempty {n | ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) n}) :=
        ⟨5, hupper⟩
      rw [csInf_eq_iff hnonempty]
      refine ⟨hupper, ?_⟩
      intro M hM
      by_contra! hlt
      exact hlower M hlt hM
compl_adj
Two distinct vertices are adjacent in the complement graph Gᶜ if and only if they are not adjacent in G.
csInf_eq_iff
For a nonempty subset of a well-ordered type, its infimum equals n if and only if n belongs to the set and is a lower bound for it.
fromRel_adj
Two vertices are adjacent in the graph generated by a relation r if and only if they are distinct and related by r in either direction.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj
The edges of the alternating path AP_3 on {0, 1, 2} are precisely {0, 2} and {1, 2}.
ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_three
An existential condition for an index m with m + 1 < 3 is equivalent to the disjunction of the cases m = 0 and m = 1.
ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases
Every strictly monotone function from Fin 3 to Fin 4 has range {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, or {1, 2, 3}.
ordered_ramsey_monotone_cycle_three_alternating_path_three_forall_lt_not_prop
For any M < 5, the ordered Ramsey property for MC_3 and AP_3 does not hold on M vertices.
ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_ap3
The 4-vertex graph G_4 contains no ordered copy of the alternating path AP_3 in its complement.
ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_mc3
The 4-vertex graph G_4 contains no ordered copy of the monotone cycle MC_3.
ordered_ramsey_monotone_cycle_three_alternating_path_three_has_ap3_compl
If three ordered vertices u < v < w in G have neither uw nor vw as edges, then Gᶜ contains an ordered copy of AP_3.
ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3
If three ordered vertices u < v < w in G are mutually adjacent, then G contains an ordered copy of MC_3.
ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top
The monotone cycle on 3 vertices MC_3 is the complete graph ⊤ on Fin 3.
ordered_ramsey_monotone_cycle_three_alternating_path_three_mono
The ordered Ramsey property is monotone: if it holds on M vertices, it holds on any N ≥ M vertices.
ordered_ramsey_monotone_cycle_three_alternating_path_three_not_prop_four
The ordered Ramsey property for MC_3 and AP_3 fails on 4 vertices.
ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_fast
If nine edge propositions on 5 vertices satisfy the AP_3-avoidance conditions for every triple, then at least one of the five triangles has all three edges present.
ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_five
Every 2-coloring of the edges of the ordered complete graph on 5 vertices contains an ordered MC_3 or an ordered AP_3 in the complement.
SimpleGraph.fromRel_adj
Two vertices are adjacent in the graph generated by a relation r if and only if they are distinct and related by r in either direction.
top_adj
Two vertices in the complete graph ⊤ are adjacent if and only if they are distinct.

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

Lean’s trace was cut to the first 400 of 510 tactics.

open SimpleGraphlemma ordered_ramsey_monotone_cycle_three_alternating_path_three_mono {α β : Type*} [LinearOrder α] [LinearOrder β]    (H : SimpleGraph α) (H' : SimpleGraph β) {M N : ℕ} (hMN : M ≤ N)    (hM : ordered_ramsey_prop H H' M) : ordered_ramsey_prop H H' N := by  intro G  let emb : Fin M → Fin N := fun x => ⟨x.val, by omega⟩  have hemb_mono : StrictMono emb := fun _ _ hxy => hxy  have hemb_inj : Function.Injective emb := hemb_mono.injective  let G' : SimpleGraph (Fin M) :=    { Adj := fun u v => G.Adj (emb u) (emb v)      symm := ⟨fun {_ _} h => G.adj_symm h⟩      loopless := ⟨fun _ h => G.irrefl h⟩ }  rcases hM G' with ⟨f, hf_mono, hf_adj⟩ | ⟨f, hf_mono, hf_adj⟩  · left    refine ⟨emb ∘ f, hemb_mono.comp hf_mono, ?_⟩    intro u v huv    exact hf_adj huv  · right    refine ⟨emb ∘ f, hemb_mono.comp hf_mono, ?_⟩    intro u v huv    have := hf_adj huv    rw [compl_adj] at this ⊢    refine ⟨fun h => this.1 (hemb_inj h), this.2⟩lemma ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_three (P : ℕ → Prop) :    (∃ m : ℕ, m + 1 < 3 ∧ P m) ↔ P 0 ∨ P 1 := by  constructor  · rintro ⟨m, hm, hp⟩    have : m = 0 ∨ m = 1 := by omega    rcases this with rfl | rfl    · left; exact hp    · right; exact hp  · rintro (h0 | h1)    · exact ⟨0, by decide, h0⟩    · exact ⟨1, by decide, h1⟩theorem ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top : monotone_cycle 3 = ⊤ := by  ext a b  simp [monotone_cycle, SimpleGraph.fromRel_adj]  fin_cases a <;> fin_cases b <;> decidetheorem ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj (a b : Fin 3) :    (alternating_path 3).Adj a b ↔ (a.val = 0 ∧ b.val = 2) ∨ (a.val = 2 ∧ b.val = 0) ∨      (a.val = 1 ∧ b.val = 2) ∨ (a.val = 2 ∧ b.val = 1) := by  simp only [alternating_path, fromRel_adj, ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_three, alternating_path_vertex]  fin_cases a <;> fin_cases b <;> decidelemma ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 {N : ℕ} (G : SimpleGraph (Fin N)) {u v w : Fin N}    (huv : u < v) (hvw : v < w) (hadj1 : G.Adj u v) (hadj2 : G.Adj v w) (hadj3 : G.Adj u w) :    has_ordered_copy G (monotone_cycle 3) := by  let f : Fin 3 → Fin N := fun x =>    if x = 0 then u else if x = 1 then v else w  refine ⟨f, ?_, ?_⟩  · intro x y hxy    fin_cases x <;> fin_cases y    · exfalso; exact lt_irrefl _ hxy    · dsimp [f]; exact huv    · dsimp [f]; exact huv.trans hvw    · exfalso; revert hxy; decide    · exfalso; exact lt_irrefl _ hxy    · dsimp [f]; exact hvw    · exfalso; revert hxy; decide    · exfalso; revert hxy; decide    · exfalso; exact lt_irrefl _ hxy  · intro x y hxy    rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj] at hxy    fin_cases x <;> fin_cases y    · exfalso; exact hxy rfl    · dsimp [f]; exact hadj1    · dsimp [f]; exact hadj3    · dsimp [f]; exact hadj1.symm    · exfalso; exact hxy rfl    · dsimp [f]; exact hadj2    · dsimp [f]; exact hadj3.symm    · dsimp [f]; exact hadj2.symm    · exfalso; exact hxy rfllemma ordered_ramsey_monotone_cycle_three_alternating_path_three_has_ap3_compl {N : ℕ} (G : SimpleGraph (Fin N)) {u v w : Fin N}    (huv : u < v) (hvw : v < w) (hnot1 : ¬ G.Adj u w) (hnot2 : ¬ G.Adj v w) :    has_ordered_copy Gᶜ (alternating_path 3) := by  let f : Fin 3 → Fin N := fun x =>    if x = 0 then u else if x = 1 then v else w  refine ⟨f, ?_, ?_⟩  · intro x y hxy    fin_cases x <;> fin_cases y    · exfalso; exact lt_irrefl _ hxy    · dsimp [f]; exact huv    · dsimp [f]; exact huv.trans hvw    · exfalso; revert hxy; decide    · exfalso; exact lt_irrefl _ hxy    · dsimp [f]; exact hvw    · exfalso; revert hxy; decide    · exfalso; revert hxy; decide    · exfalso; exact lt_irrefl _ hxy  · intro x y hxy    rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj] at hxy    rw [compl_adj]    fin_cases x <;> fin_cases y    · exfalso; revert hxy; decide    · exfalso; revert hxy; decide    · dsimp [f]; exact ⟨(huv.trans hvw).ne, hnot1⟩    · exfalso; revert hxy; decide    · exfalso; revert hxy; decide    · dsimp [f]; exact ⟨hvw.ne, hnot2⟩    · dsimp [f]; exact ⟨(huv.trans hvw).ne', fun h => hnot1 (G.adj_symm h)⟩    · dsimp [f]; exact ⟨hvw.ne', fun h => hnot2 (G.adj_symm h)⟩    · exfalso; revert hxy; decidetheorem ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_fast    (e02 e12 e03 e13 e23 e04 e14 e24 e34 : Prop)    (h012 : e02 ∨ e12)    (h013 : e03 ∨ e13)    (h023 : e03 ∨ e23)    (h123 : e13 ∨ e23)    (h014 : e04 ∨ e14)    (h024 : e04 ∨ e24)    (h034 : e04 ∨ e34)    (h124 : e14 ∨ e24)    (h134 : e14 ∨ e34)    (h234 : e24 ∨ e34) :    (e02 ∧ e24 ∧ e04) ∨    (e12 ∧ e24 ∧ e14) ∨    (e03 ∧ e34 ∧ e04) ∨    (e13 ∧ e34 ∧ e14) ∨    (e23 ∧ e34 ∧ e24) := by  by_cases h34 : e34  · by_cases h24 : e24    · by_cases h23 : e23      · right; right; right; right; exact ⟨h23, h34, h24⟩      · have he03 : e03 := by rcases h023 with h | h; exact h; contradiction        have he13 : e13 := by rcases h123 with h | h; exact h; contradiction        rcases h014 with he04 | he14        · right; right; left; exact ⟨he03, h34, he04⟩        · right; right; right; left; exact ⟨he13, h34, he14⟩    · have he04 : e04 := by rcases h024 with h | h; exact h; contradiction      have he14 : e14 := by rcases h124 with h | h; exact h; contradiction      rcases h013 with he03 | he13      · right; right; left; exact ⟨he03, h34, he04⟩      · right; right; right; left; exact ⟨he13, h34, he14⟩  · have he04 : e04 := by rcases h034 with h | h; exact h; contradiction    have he14 : e14 := by rcases h134 with h | h; exact h; contradiction    have he24 : e24 := by rcases h234 with h | h; exact h; contradiction    rcases h012 with he02 | he12    · left; exact ⟨he02, he24, he04⟩    · right; left; exact ⟨he12, he24, he14⟩lemma ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_five :    ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) 5 := by  intro G  by_cases h_ap : has_ordered_copy Gᶜ (alternating_path 3)  · right; exact h_ap  · left    have H_ap : ∀ ⦃u v w : Fin 5⦄, u < v → v < w → G.Adj u w ∨ G.Adj v w := by      intro u v w huv hvw      by_contra! h      exact h_ap (ordered_ramsey_monotone_cycle_three_alternating_path_three_has_ap3_compl G huv hvw h.1 h.2)    have h_tri := ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_fast      (G.Adj 0 2) (G.Adj 1 2) (G.Adj 0 3) (G.Adj 1 3) (G.Adj 2 3)      (G.Adj 0 4) (G.Adj 1 4) (G.Adj 2 4) (G.Adj 3 4)      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))      (H_ap (by decide) (by decide))    rcases h_tri with ⟨h02, h24, h04⟩ | ⟨h12, h24, h14⟩ | ⟨h03, h34, h04⟩ | ⟨h13, h34, h14⟩ | ⟨h23, h34, h24⟩    · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h02 h24 h04    · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h12 h24 h14    · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h03 h34 h04    · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h13 h34 h14    · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_has_mc3 G (by decide) (by decide) h23 h34 h24def ordered_ramsey_monotone_cycle_three_alternating_path_three_G4 : SimpleGraph (Fin 4) where  Adj u v := (u.val = 0 ∧ v.val = 2) ∨ (u.val = 2 ∧ v.val = 0) ∨             (u.val = 0 ∧ v.val = 3) ∨ (u.val = 3 ∧ v.val = 0) ∨             (u.val = 1 ∧ v.val = 3) ∨ (u.val = 3 ∧ v.val = 1)  symm := ⟨by    intro u v h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩    · right; left; exact ⟨h2, h1⟩    · left; exact ⟨h2, h1⟩    · right; right; right; left; exact ⟨h2, h1⟩    · right; right; left; exact ⟨h2, h1⟩    · right; right; right; right; right; exact ⟨h2, h1⟩    · right; right; right; right; left; exact ⟨h2, h1⟩⟩  loopless := ⟨by    intro u h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega⟩lemma ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases (f : Fin 3 → Fin 4) (hf : StrictMono f) :    (f 0 = 0 ∧ f 1 = 1 ∧ f 2 = 2) ∨    (f 0 = 0 ∧ f 1 = 1 ∧ f 2 = 3) ∨    (f 0 = 0 ∧ f 1 = 2 ∧ f 2 = 3) ∨    (f 0 = 1 ∧ f 1 = 2 ∧ f 2 = 3) := by  have h01 := hf (by decide : (0 : Fin 3) < 1)  have h12 := hf (by decide : (1 : Fin 3) < 2)  generalize ha : f 0 = a at h01 ⊢  generalize hb : f 1 = b at h01 h12 ⊢  generalize hc : f 2 = c at h12 ⊢  fin_cases a <;> fin_cases b <;> fin_cases c <;> omegalemma ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_mc3 :    ¬ has_ordered_copy ordered_ramsey_monotone_cycle_three_alternating_path_three_G4 (monotone_cycle 3) := by  intro ⟨f, hf_mono, hf_adj⟩  have h_cases := ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases f hf_mono  have htop : ∀ ⦃u v : Fin 3⦄, u ≠ v → ordered_ramsey_monotone_cycle_three_alternating_path_three_G4.Adj (f u) (f v) := by    intro u v huv    apply hf_adj    rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top, top_adj]    exact huv  rcases h_cases with ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩  · have h := htop (by decide : (0 : Fin 3) ≠ 1)    rw [h0, h1] at h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega  · have h := htop (by decide : (0 : Fin 3) ≠ 1)    rw [h0, h1] at h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega  · have h := htop (by decide : (1 : Fin 3) ≠ 2)    rw [h1, h2] at h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega  · have h := htop (by decide : (0 : Fin 3) ≠ 1)    rw [h0, h1] at h    rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omegalemma ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_ap3 :    ¬ has_ordered_copy ordered_ramsey_monotone_cycle_three_alternating_path_three_G4ᶜ (alternating_path 3) := by  intro ⟨f, hf_mono, hf_adj⟩  have h_cases := ordered_ramsey_monotone_cycle_three_alternating_path_three_fin3_fin4_mono_cases f hf_mono  have hap : ∀ ⦃u v : Fin 3⦄, (alternating_path 3).Adj u v → ¬ ordered_ramsey_monotone_cycle_three_alternating_path_three_G4.Adj (f u) (f v) := by    intro u v huv    have := hf_adj huv    rw [compl_adj] at this    exact this.2  have h02 : (alternating_path 3).Adj 0 2 := by    rw [ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj]    decide  rcases h_cases with ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩ | ⟨h0, h1, h2⟩  · have h := hap h02    rw [h0, h2] at h    apply h    left; decide  · have h := hap h02    rw [h0, h2] at h    apply h    right; right; left; decide  · have h := hap h02    rw [h0, h2] at h    apply h    right; right; left; decide  · have h := hap h02    rw [h0, h2] at h    apply h    right; right; right; right; left; decidelemma ordered_ramsey_monotone_cycle_three_alternating_path_three_not_prop_four :    ¬ ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) 4 := by  intro hprop  rcases hprop ordered_ramsey_monotone_cycle_three_alternating_path_three_G4 with h | h  · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_mc3 h  · exact ordered_ramsey_monotone_cycle_three_alternating_path_three_G4_not_ap3 hlemma ordered_ramsey_monotone_cycle_three_alternating_path_three_forall_lt_not_prop (M : ℕ) (hM : M < 5) :    ¬ ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) M := by  intro hprop  have h4 : ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) 4 :=    ordered_ramsey_monotone_cycle_three_alternating_path_three_mono _ _ (by omega) hprop  exact ordered_ramsey_monotone_cycle_three_alternating_path_three_not_prop_four h4/-- The ordered Ramsey number of the monotone cycle MC_3 versus the alternating path AP_3 is 5. -/theorem ordered_ramsey_monotone_cycle_three_alternating_path_three :    ordered_ramsey_number (monotone_cycle 3) (alternating_path 3) = 5 := by  have hupper := ordered_ramsey_monotone_cycle_three_alternating_path_three_prop_five  have hlower := ordered_ramsey_monotone_cycle_three_alternating_path_three_forall_lt_not_prop  dsimp [ordered_ramsey_number]  have hnonempty : (Set.Nonempty {n | ordered_ramsey_prop (monotone_cycle 3) (alternating_path 3) n}) :=    ⟨5, 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