AFTD Auto-Formalizing Theoretical Domains

alternating_path

def

The alternating path AP_n is the ordered simple graph on Fin n whose edges connect consecutive vertices in the alternating sequence 0, n-1, 1, n-2, ....

Statement

def alternating_path (n : ℕ) : SimpleGraph (Fin n)
Defined in
arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • 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.
Used by 3

Read back from the Lean

For any natural number n, alternating_path n is defined as the simple graph on the vertex type Fin n obtained via SimpleGraph.fromRel from the directed relation: vertex a is related to vertex b if and only if there exists a natural number m such that m + 1 < n, a.val = alternating_path_vertex n m, and b.val = alternating_path_vertex n (m + 1). Equivalently, two vertices a, b : Fin n are adjacent in alternating_path n if and only if a ≠ b and there exists a natural number m with m + 1 < n such that either: 1. a.val = alternating_path_vertex n m and b.val = alternating_path_vertex n (m + 1), or 2. b.val = alternating_path_vertex n m and a.val = alternating_path_vertex n (m + 1). Here, alternating_path_vertex n m is defined as m / 2 if m is even (m % 2 = 0), and n - 1 - m / 2 if m is odd.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The alternating path AP_n on Fin n whose vertices in path order alternate from the ends inward. -/
def alternating_path (n : ℕ) : SimpleGraph (Fin n) := SimpleGraph.fromRel (fun a b =>
    ∃ m : ℕ, m + 1 < n ∧ a.val = alternating_path_vertex n m ∧ b.val = alternating_path_vertex n (m + 1))
See it in the graphDiscuss this resultChallenge it