AFTD Auto-Formalizing Theoretical Domains

orientation_tuple_is_pfaffian

def

For n K : ℕ, a simple graph G : SimpleGraph (Fin n) and a K-tuple of digraphs D : Fin K → Digraph (Fin n): there is x : Fin K → ℝ such that for every perfect matching M of G (M : G.Subgraph with M.IsPerfectMatching), ∑ over j : Fin K of (orientation_perfect_matching_sign (D j) M : ℝ) * x j = 1; that is, the signature system sign_D x = 1 has a real solution.

Statement

def orientation_tuple_is_pfaffian {n K : ℕ} (G : SimpleGraph (Fin n))
    (D : Fin K → Digraph (Fin n)) : Prop
Defined in
arXiv:2611.00468 (The symbolic pfaffian method I), Section 1.1, pfaffian k-orientation (the system sign_D x = 1 solved over ℝ)
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • orientation_perfect_matching_signFor n : ℕ, a simple graph G : SimpleGraph (Fin n) (implicit), a digraph D : Digraph (Fin n) and a subgraph M : G.Subgraph, the integer…
Used by 1

Read back from the Lean

Given natural numbers n and K, a simple graph G on vertices Fin n, and a family of K directed graphs D : Fin K → Digraph (Fin n), the declaration orientation_tuple_is_pfaffian G D asserts that: There exists a real vector x : Fin K → ℝ such that for every subgraph M of G, if M is a perfect matching of G, then: ∑ (j : Fin K), (orientation_perfect_matching_sign (D j) M : ℝ) * x j = 1, where for any directed graph D' and subgraph M, orientation_perfect_matching_sign D' M is defined as: - If there exists a permutation π of Fin n such that for all natural numbers j with 2 * j + 1 < n, (π(2j), π(2j+1)) is an edge in M and a directed edge in D', then the sign (±1 as an integer) of the permutation chosen by Classical.choose satisfying this condition; - Otherwise, 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

/-- A tuple of orientations is pfaffian when its signature system has a real solution. -/
def orientation_tuple_is_pfaffian {n K : ℕ} (G : SimpleGraph (Fin n))
    (D : Fin K → Digraph (Fin n)) : Prop :=
  ∃ x : Fin K → ℝ, ∀ M : G.Subgraph, M.IsPerfectMatching →
    ∑ j, (orientation_perfect_matching_sign (D j) M : ℝ) * x j = 1
See it in the graphDiscuss this resultChallenge it