AFTD Auto-Formalizing Theoretical Domains

orientation_perfect_matching_sign

def

For n : ℕ, a simple graph G : SimpleGraph (Fin n) (implicit), a digraph D : Digraph (Fin n) and a subgraph M : G.Subgraph, the integer sign of M in D: if some permutation π : Equiv.Perm (Fin n) lists the edges of M in consecutive pairs, oriented by D -- for every natural j with 2j+1 < n, M.Adj (π (2j)) (π (2j+1)) and D.Adj (π (2j)) (π (2j+1)) -- then it is the sign of such a permutation (one chosen by Classical.choice), as the integer 1 or -1; otherwise it is 0.

Statement

open Classical in
noncomputable def orientation_perfect_matching_sign {n : ℕ} {G : SimpleGraph (Fin n)}
    (D : Digraph (Fin n)) (M : G.Subgraph) : ℤ
Defined in
arXiv:2611.00468 (The symbolic pfaffian method I), Section 1.1, the sign sign_D(M) of a perfect matching (vertices enumerated as Fin n; value 0 when no listing exists)
Verified
07 Nov 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given a natural number n, a simple graph G on Fin n (implicit), a directed graph D on Fin n, and a subgraph M of G, orientation_perfect_matching_sign D M is the integer defined by: If there exists a permutation π of Fin n such that for every natural number j with 2 * j + 1 < n, π(2 * j) and π(2 * j + 1) are adjacent in M and there is a directed edge from π(2 * j) to π(2 * j + 1) in D, then it returns the sign of the permutation chosen by Classical.choose from that existential statement (as an integer in {1, -1}). Otherwise, it returns 0.

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

open Classical in
/-- The sign of a perfect matching `M` in an orientation `D` of a graph on `Fin n`. -/
noncomputable def orientation_perfect_matching_sign {n : ℕ} {G : SimpleGraph (Fin n)}
    (D : Digraph (Fin n)) (M : G.Subgraph) : ℤ :=
  if h : ∃ π : Equiv.Perm (Fin n), ∀ (j : ℕ) (hj : 2 * j + 1 < n),
      M.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) ∧ D.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩)
  then ((Equiv.Perm.sign h.choose : ℤˣ) : ℤ) else 0
See it in the graphDiscuss this resultChallenge it