AFTD Auto-Formalizing Theoretical Domains

orientation_tuple_is_pfaffian_of_rows_differ_in_half

theoremverifiedformalization

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

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.

  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.

    lines 10–14

    uses Finite.of_injective, Prod.mk.injEq, SimpleGraph.Subgraph.ext

      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)
  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.

    lines 15–30

    uses pm_one_rows_differ_in_half_exists_solution, orientation_perfect_matching_sign_eq_one_or_neg_one, congrFun, ne_eq, Int.cast_inj

      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)
  3. 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.

    line 31

      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).

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

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⟩⟩
See it in the graphDiscuss this resultChallenge it