orientation_tuple_is_pfaffian_of_rows_differ_in_half
Let 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 (is_graph_orientation G (D j) for every j). Suppose that any two perfect matchings M, N of G whose sign vectors (orientation_perfect_matching_sign (D j) M)_j and (orientation_perfect_matching_sign (D j) N)_j are different differ in exactly k coordinates j. Then D is pfaffian (orientation_tuple_is_pfaffian G D).
Statement
theorem orientation_tuple_is_pfaffian_of_rows_differ_in_half {n k : ℕ} (hk : 1 ≤ k) (G : SimpleGraph (Fin n)) (D : Fin (2 * k) → Digraph (Fin n)) (hD : ∀ j, is_graph_orientation G (D j)) (hrows : ∀ M N : G.Subgraph, M.IsPerfectMatching → N.IsPerfectMatching → (fun j => orientation_perfect_matching_sign (D j) M) ≠ (fun j => orientation_perfect_matching_sign (D j) N) → (Finset.univ.filter fun j => orientation_perfect_matching_sign (D j) M ≠ orientation_perfect_matching_sign (D j) N).card = k) : orientation_tuple_is_pfaffian G D
- Formalizes
- arXiv:2611.00468 (The symbolic pfaffian method I), Lemma 2.1 (vertices Fin n; 'different rows' read as perfect matchings with different sign vectors; the solution is over ℝ; k ≥ 1 explicit)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_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…
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
- pm_one_rows_differ_in_half_exists_solutionLet k ≥ 1 and let A : ι → Fin (2k) → ℝ be a finite family of rows with entries ±1. If any two distinct rows differ in exactly k…
- 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…
Read back from the Lean
Let $n, k \in \mathbb{N}$ with $1 \le k$. Let $G$ be a simple graph on vertex set Fin n, and let $D$ be a family of $2k$ directed graphs on Fin n (indexed by Fin (2 * k)).
Assume that:
1. For every $j \in \text{Fin}(2k)$, $D(j)$ is an orientation of $G$ (is_graph_orientation G (D j)).
2. For all subgraphs $M$ and $N$ of $G$, if both $M$ and $N$ are perfect matchings of $G$ (M.IsPerfectMatching and N.IsPerfectMatching), and the tuple of signs $(\text{orientation\_perfect\_matching\_sign}(D(j), M))_{j \in \text{Fin}(2k)}$ is not equal to $(\text{orientation\_perfect\_matching\_sign}(D(j), N))_{j \in \text{Fin}(2k)}$, then the number of indices $j \in \text{Fin}(2k)$ where $\text{orientation\_perfect\_matching\_sign}(D(j), M) \neq \text{orientation\_perfect\_matching\_sign}(D(j), N)$ is exactly $k$.
Then $D$ is a Pfaffian tuple of orientations for $G$ (orientation_tuple_is_pfaffian G D), meaning there exists a vector $x : \text{Fin}(2k) \to \mathbb{R}$ such that for every subgraph $M$ of $G$, if $M$ is a perfect matching, then
$$\sum_{j \in \text{Fin}(2k)} (\text{orientation\_perfect\_matching\_sign}(D(j), M) : \mathbb{R}) \cdot x(j) = 1.$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that a 2k-tuple of orientations D is Pfaffian by casting the problem into a linear system on the sign vectors of perfect matchings. Because the graph has finitely many vertices, the set of all perfect matchings is finite, allowing us to view the orientation signs as a matrix with entries in {1, -1}. By hypothesis, any two distinct rows differ in exactly half of their coordinates (k out of 2k). The result then follows from the general combinatorial lemma pm_one_rows_differ_in_half_exists_solution, which guarantees that such a ±1 matrix admits a solution vector summing each row to 1.
The collection of all subgraphs of G is a finite type.
Under classical logic, a subgraph H is uniquely determined by its vertex set and its adjacency relation. Since G has vertices in the finite type Fin n, the type of pairs of vertex subsets and adjacency relations is finite. By SimpleGraph.Subgraph.ext and Prod.mk.injEq, the map sending a subgraph H to the pair (H.verts, H.Adj) is injective. Applying Finite.of_injective shows that G.Subgraph is finite, which in turn implies that the subtype of perfect matchings of G is finite.
uses
Finite.of_injective,Prod.mk.injEq,SimpleGraph.Subgraph.extclassical have hfin : Finite G.Subgraph := Finite.of_injective (fun H : G.Subgraph => (H.verts, H.Adj)) (fun a b h => by simp only [Prod.mk.injEq] at h exact SimpleGraph.Subgraph.ext h.1 h.2)
There exists a real weighting vector x : Fin (2k) → ℝ such that ∑_{j=0}^{2k-1} sign(D_j, M) · x_j = 1 for every perfect matching M of G.
We apply the general theorem pm_one_rows_differ_in_half_exists_solution to the matrix A whose rows are indexed by perfect matchings of G and columns by Fin (2k), defined by A(M, j) = sign(D_j, M). The theorem requires two conditions: first, every entry is ±1, which is established by orientation_perfect_matching_sign_eq_one_or_neg_one. Second, any two distinct rows of A differ in exactly k coordinates: if two rows are distinct in ℝ^{2k}, their integer sign vectors must also be distinct (by congrFun), so by the hypothesis hrows, the integer sign vectors differ in exactly k positions. Because casting from ℤ to ℝ is injective (Int.cast_inj, using ne_eq), the real rows also differ in exactly k coordinates. The theorem then yields the desired vector x.
uses
pm_one_rows_differ_in_half_exists_solution,orientation_perfect_matching_sign_eq_one_or_neg_one,congrFun,ne_eq,Int.cast_injobtain ⟨x, hx⟩ := pm_one_rows_differ_in_half_exists_solution hk (ι := {M : G.Subgraph // M.IsPerfectMatching}) (fun M j => (orientation_perfect_matching_sign (D j) M.1 : ℝ)) (fun M j => by rcases orientation_perfect_matching_sign_eq_one_or_neg_one G (D j) (hD j) M.1 M.2 with h | h · left; simp [h] · right; simp [h]) (fun M N hne => by have hne' : (fun j => orientation_perfect_matching_sign (D j) M.1) ≠ (fun j => orientation_perfect_matching_sign (D j) N.1) := by intro h apply hne funext j simp only [congrFun h j] have := hrows M.1 N.1 M.2 N.2 hne' simpa only [ne_eq, Int.cast_inj] using this)
The orientation tuple D is Pfaffian.
By definition, D being Pfaffian (orientation_tuple_is_pfaffian G D) means there exists a vector x such that ∑_j sign(D_j, M) · x_j = 1 for every perfect matching M. The vector x constructed in the previous step satisfies this condition for every perfect matching, which completes the proof.
exact ⟨x, fun M hM => hx ⟨M, hM⟩⟩
Finite.of_injective- If f : α → β is an injective function and β is a finite type, then α is also finite.
Prod.mk.injEq- Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
SimpleGraph.Subgraph.ext- Two subgraphs of a graph are equal if and only if they have the same vertex set and the same adjacency relation.
pm_one_rows_differ_in_half_exists_solution- For any matrix with entries in {1, -1} with 2k columns (k ≥ 1) whose row index set is finite, if every pair of distinct rows differs in exactly k coordinates, then there exists a vector x such that the row sums weighted by x are all equal to 1.
orientation_perfect_matching_sign_eq_one_or_neg_one- For any orientation D of a graph G and any perfect matching M, the orientation sign of M with respect to D is either 1 or -1.
congrFun- If two functions f and g are equal, then f(a) = g(a) for all inputs a.
ne_eq- The inequality a ≠ b is defined as ¬(a = b).
Int.cast_inj- The canonical cast from integers to real numbers is injective (m = n if and only if ↑m = ↑n).
- Lean formalizes the row index set as the subtype {M : G.Subgraph // M.IsPerfectMatching}, requiring an explicit finiteness proof (Finite G.Subgraph) before applying the general linear algebraic lemma. On paper, finiteness is immediate because the graph has finitely many vertices.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem orientation_tuple_is_pfaffian_of_rows_differ_in_half {n k : ℕ} (hk : 1 ≤ k) (G : SimpleGraph (Fin n)) (D : Fin (2 * k) → Digraph (Fin n)) (hD : ∀ j, is_graph_orientation G (D j)) (hrows : ∀ M N : G.Subgraph, M.IsPerfectMatching → N.IsPerfectMatching → (fun j => orientation_perfect_matching_sign (D j) M) ≠ (fun j => orientation_perfect_matching_sign (D j) N) → (Finset.univ.filter fun j => orientation_perfect_matching_sign (D j) M ≠ orientation_perfect_matching_sign (D j) N).card = k) : orientation_tuple_is_pfaffian G D := by classical have hfin : Finite G.Subgraph := Finite.of_injective (fun H : G.Subgraph => (H.verts, H.Adj)) (fun a b h => by simp only [Prod.mk.injEq] at h exact SimpleGraph.Subgraph.ext h.1 h.2) obtain ⟨x, hx⟩ := pm_one_rows_differ_in_half_exists_solution hk (ι := {M : G.Subgraph // M.IsPerfectMatching}) (fun M j => (orientation_perfect_matching_sign (D j) M.1 : ℝ)) (fun M j => by rcases orientation_perfect_matching_sign_eq_one_or_neg_one G (D j) (hD j) M.1 M.2 with h | h · left; simp [h] · right; simp [h]) (fun M N hne => by have hne' : (fun j => orientation_perfect_matching_sign (D j) M.1) ≠ (fun j => orientation_perfect_matching_sign (D j) N.1) := by intro h apply hne funext j simp only [congrFun h j] have := hrows M.1 N.1 M.2 N.2 hne' simpa only [ne_eq, Int.cast_inj] using this) exact ⟨x, fun M hM => hx ⟨M, hM⟩⟩