orientation_perfect_matching_sign
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
- orientation_perfect_matching_sign_eq_one_or_neg_oneIf D is an orientation of a simple graph G on Fin n (is_graph_orientation G D) and M is a perfect matching of G, then…
- orientation_tuple_is_pfaffianFor 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…
- 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…
- orientation_perfect_matching_sign_twoIn the complete graph on Fin 2, the perfect matching consisting of its single edge, oriented from 0 to 1, has sign 1.
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