ordered_ramsey_monotone_cycle_three_alternating_path_three
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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ᶜ.
uses
compl_adjintro 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⟩
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.
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⟩
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.
uses
SimpleGraph.fromRel_adjext a b simp [monotone_cycle, SimpleGraph.fromRel_adj] fin_cases a <;> fin_cases b <;> decide
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}.
uses
fromRel_adj,ordered_ramsey_monotone_cycle_three_alternating_path_three_exists_m_threesimp 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
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.
uses
lt_irrefl,ordered_ramsey_monotone_cycle_three_alternating_path_three_mc3_eq_top,top_adjlet 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
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ᶜ.
uses
lt_irrefl,ordered_ramsey_monotone_cycle_three_alternating_path_three_ap3_adj,compl_adjlet 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
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.
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⟩
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.
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_mc3intro 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
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.
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⟩
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.
(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 <;> omegaG_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}.
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
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.
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
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.
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
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.
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
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.
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_iffordered_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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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