ordered_ramsey_monotone_cycle_alternating_path_two
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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.
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 ⊤.
uses
SimpleGraph.fromRelhave _ := 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
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.
uses
strictMono_id,SimpleGraph.top_adjhave 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
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 ≠ ⊤.
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
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ᶜ.
uses
lt_irrefl,SimpleGraph.top_adj,SimpleGraph.compl_adjrcases 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
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.
uses
Fintype.card_le_of_injective,Fintype.card_fin,SimpleGraph.top_adj,compl_tophave 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
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).
uses
csInf_eq_iffdsimp [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
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.
/-- 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