AFTD Auto-Formalizing Theoretical Domains

is_admissible_diagonal_selection

def

A selection M of unit diagonals on the grid V_{2k-1} = {0, ..., 2k-1}^2 is admissible if its edges are unit diagonals, have pairwise disjoint endpoints, and no unit square contains both of its diagonals.

Statement

def is_admissible_diagonal_selection (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Prop
Defined in
arXiv:2610.33042 Section 1 and Section 2
Verified
27 Oct 2026
Axioms
none listed

Read back from the Lean

A predicate is_admissible_diagonal_selection k M asserting that, for a given natural number k and a finite set M of unordered pairs of vertices in Fin (2 * k) × Fin (2 * k), all of the following hold: 1. **Every edge is a unit-square diagonal**: For every e ∈ M, there exist vertices u and v such that e = s(u, v) (the unordered pair of u and v), and there exist natural numbers r and c with r + 1 < 2 * k and c + 1 < 2 * k such that either: - u = (r, c) and v = (r + 1, c + 1) (or vice-versa), or - u = (r, c + 1) and v = (r + 1, c) (or vice-versa). 2. **Vertex-disjointness**: For all e₁, e₂ ∈ M, if e₁ ≠ e₂, then e₁ and e₂ share no vertices (for every vertex v, if v ∈ e₁ then v ∉ e₂). 3. **No crossing diagonals**: For all natural numbers r and c with r + 1 < 2 * k and c + 1 < 2 * k, M does not contain both diagonals of the unit square [r, r+1] × [c, c+1], i.e., it is not the case that both s((r, c), (r + 1, c + 1)) ∈ M and s((r, c + 1), (r + 1, c)) ∈ M.

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

/-- An admissible selection of unit diagonals on V_{2k-1} is a matching of unit diagonals containing at most one diagonal from each unit square. -/
def is_admissible_diagonal_selection (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Prop := (∀ e ∈ M, ∃ u v, e = s(u, v) ∧
    ((∃ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k),
      (u = (⟨r, by omega⟩, ⟨c, by omega⟩) ∧ v = (⟨r + 1, hr⟩, ⟨c + 1, hc⟩) ∨
       u = (⟨r + 1, hr⟩, ⟨c + 1, hc⟩) ∧ v = (⟨r, by omega⟩, ⟨c, by omega⟩))) ∨
     (∃ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k),
      (u = (⟨r, by omega⟩, ⟨c + 1, hc⟩) ∧ v = (⟨r + 1, hr⟩, ⟨c, by omega⟩) ∨
       u = (⟨r + 1, hr⟩, ⟨c, by omega⟩) ∧ v = (⟨r, by omega⟩, ⟨c + 1, hc⟩))))) ∧
  (∀ e₁ ∈ M, ∀ e₂ ∈ M, e₁ ≠ e₂ → ∀ v, v ∈ e₁ → v ∉ e₂) ∧
  (∀ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k),
    ¬ (s((⟨r, by omega⟩, ⟨c, by omega⟩), (⟨r + 1, hr⟩, ⟨c + 1, hc⟩)) ∈ M ∧
       s((⟨r, by omega⟩, ⟨c + 1, hc⟩), (⟨r + 1, hr⟩, ⟨c, by omega⟩)) ∈ M))
See it in the graphDiscuss this resultChallenge it