orientation_tuple_is_pfaffian
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
- orientation_tuple_is_pfaffian_of_rows_differ_in_halfLet k ≥ 1, let G be a simple graph on Fin n and let D : Fin (2k) → Digraph (Fin n) be a 2k-tuple of orientations of G…
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