AFTD Auto-Formalizing Theoretical Domains

nested_matching

def

The nested matching NM_{2k} is the cyclically ordered simple graph on 2k vertices with edges {i, 2k - 1 - i} for 0 ≤ i < k.

Statement

def nested_matching (k : ℕ) : SimpleGraph (Fin (2 * k))
Defined in
arXiv:2611.08375, Sec. 1
Verified
06 Nov 2026
Axioms
none listed
Used by 2
  • op_1258_cyclic_ramsey_k2_l3The cyclic Ramsey number R_cyc(NM_4, MP_3) of the 2-edge nested matching NM_4 and the monotone path MP_3 is equal to 4.
  • op_1258_cyclic_ramsey_k_oneFor every integer l ≥ 3, the cyclic Ramsey number R_cyc(NM_2, MP_l) of the 1-edge nested matching and the monotone path MP_l equals l.

Read back from the Lean

For any natural number k, nested_matching k is the simple graph on the vertex type Fin (2 * k) constructed via SimpleGraph.fromRel from the relation fun u v => u.val + v.val + 1 = 2 * k. Explicitly, two vertices u, v : Fin (2 * k) are adjacent if and only if (u.val + v.val + 1 = 2 * k ∨ v.val + u.val + 1 = 2 * k) ∧ u ≠ v, which simplifies to u.val + v.val + 1 = 2 * k (since addition is commutative and 2 * u.val + 1 = 2 * k has no solution in natural numbers, guaranteeing u ≠ v).

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 cyclically ordered nested matching on 2k vertices. -/
def nested_matching (k : ℕ) : SimpleGraph (Fin (2 * k)) := SimpleGraph.fromRel fun u v => u.val + v.val + 1 = 2 * k
See it in the graphDiscuss this resultChallenge it