orientation_perfect_matching_sign_eq_one_or_neg_one
If 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_perfect_matching_sign D M is 1 or -1.
Statement
theorem orientation_perfect_matching_sign_eq_one_or_neg_one {n : ℕ} (G : SimpleGraph (Fin n))
(D : Digraph (Fin n)) (hD : is_graph_orientation G D) (M : G.Subgraph)
(hM : M.IsPerfectMatching) :
orientation_perfect_matching_sign D M = 1 ∨ orientation_perfect_matching_sign D M = -1- Source
- arXiv:2611.00468 (The symbolic pfaffian method I), Section 1.1 (the sign of a perfect matching is ±1)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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…
The proof, explained
A perfect matching M pairs each vertex v with a unique partner p(v), making p an involution. Since D is an orientation of G, for each matched pair {v, p(v)}, exactly one of the directed edges (v, p(v)) or (p(v), v) belongs to D. The vertices v whose matching edge is directed as v → p(v) form a subset T of size n / 2 that partitions the vertex set with p(T). Interleaving the elements of T at even indices and their partners at odd indices yields a permutation π whose consecutive pairs are directed matching edges, which ensures by definition that the sign of the matching is 1 or -1.
Each vertex v has a unique neighbor p(v) in the matching M, and the resulting partner map p is an involution (hence injective).
Since M is a perfect matching, every vertex v in Fin n has a unique adjacent vertex in M. We choose a function p : Fin n → Fin n such that v and p(v) are adjacent in M for all v. By symmetry of adjacency, p(v) is adjacent to v, so by uniqueness of the neighbor of p(v), p(p(v)) = v. Since p ∘ p is the identity, p is injective.
classical -- the partner map have hex : ∀ v, ∃! w, M.Adj v w := fun v => hM.1 (hM.2 v) choose p hp huniq using hex have hpp : ∀ v, p (p v) = v := fun v => (huniq (p v) v (hp v).symm).symm have hpinj : Function.Injective p := fun a b h => by rw [← hpp a, h, hpp b]
Defining T as the set of vertices whose matching edge is directed towards their partner in D, exactly one of {v, p(v)} belongs to T for every vertex v.
Let T be the set of vertices v with a directed edge v → p(v) in D. Because the matching edge {v, p(v)} belongs to G and D is an orientation of G, exactly one of the directed edges (v, p(v)) or (p(v), v) belongs to D. Since p(p(v)) = v, p(v) ∈ T is equivalent to (p(v), v) ∈ D, which is the negation of (v, p(v)) ∈ D, so v ∈ T ↔ p(v) ∉ T.
uses
Finset.mem_filter,Finset.mem_univ,true_andset T : Finset (Fin n) := Finset.univ.filter (fun v => D.Adj v (p v)) with hT have hxor : ∀ v, v ∈ T ↔ p v ∉ T := by intro v have hG : G.Adj v (p v) := M.adj_sub (hp v) have h1 := (hD.1 v (p v)).mpr hG have h2 := hD.2 v (p v) simp only [hT, Finset.mem_filter, Finset.mem_univ, true_and, hpp] tauto
The sets T and p(T) partition Fin n, so 2 * |T| = n.
Every vertex v belongs to either T or p(T), but not both: if a ∈ T and a = p(b) with b ∈ T, then by the previous equivalence p(b) ∉ T, a contradiction. Furthermore, if v ∉ T, then p(v) ∈ T and v = p(p(v)) ∈ p(T), so T ∪ p(T) is the entire vertex set Fin n. Since p is injective, |p(T)| = |T|. Because T and p(T) are disjoint, |T| + |p(T)| = 2 * |T| = n.
uses
Finset.disjoint_left,Finset.mem_image.mp,Finset.mem_union,Finset.mem_image,Finset.mem_univ,iff_true,Or.inl,Finset.card_union_of_disjoint,Finset.card_univ,Fintype.card_fin,Finset.card_image_of_injectivehave hcard : 2 * T.card = n := by have hdisj : Disjoint T (T.image p) := by rw [Finset.disjoint_left] intro a ha hb obtain ⟨b, hbT, rfl⟩ := Finset.mem_image.mp hb exact ((hxor b).mp hbT) ha have hunion : T ∪ T.image p = Finset.univ := by ext v simp only [Finset.mem_union, Finset.mem_image, Finset.mem_univ, iff_true] by_cases hv : v ∈ T · exact Or.inl hv · right; exact ⟨p v, (hxor (p v)).mpr (by rw [hpp]; exact hv), hpp v⟩ have := Finset.card_union_of_disjoint hdisj rw [hunion, Finset.card_univ, Fintype.card_fin, Finset.card_image_of_injective _ hpinj] at this omega
We construct a permutation π of Fin n pairing each element of T at an even index with its partner at the following odd index.
Let m = |T|, so n = 2m, and let e : Fin m → Fin n enumerate the elements of T. Define f : Fin n → Fin n by sending even indices 2j to e(j) and odd indices 2j + 1 to p(e(j)). By case analysis on parities and using that T and p(T) are disjoint while e and p are injective, f is injective. Since Fin n is finite, f is bijective and yields a permutation π.
uses
Subtype.ext,congrArg,Fin.val,Equiv.ofBijective,Finite.injective_iff_bijective.mpset m := T.card with hm let e : Fin m → Fin n := fun i => (T.equivFin.symm i : Fin n) have he_mem : ∀ i, e i ∈ T := fun i => (T.equivFin.symm i).2 have he_inj : Function.Injective e := fun a b h => T.equivFin.symm.injective (Subtype.ext h) let f : Fin n → Fin n := fun i => if i.val % 2 = 0 then e ⟨i.val / 2, by omega⟩ else p (e ⟨i.val / 2, by omega⟩) have hf_inj : Function.Injective f := by intro a b hab simp only [f] at hab split_ifs at hab with ha hb hb · have := congrArg Fin.val (he_inj hab); simp at this; ext; omega · exact absurd (hab ▸ he_mem _) ((hxor _).mp (he_mem _)) · exact absurd (hab.symm ▸ he_mem _) ((hxor _).mp (he_mem _)) · have := congrArg Fin.val (he_inj (hpinj hab)); simp at this; ext; omega let π : Equiv.Perm (Fin n) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf_inj)
The permutation π aligns each consecutive pair (π(2j), π(2j+1)) with a matching edge directed in D.
For each j with 2j + 1 < n, evaluating f gives π(2j) = e(j) and π(2j + 1) = p(e(j)). The pair (e(j), p(e(j))) is an edge of M by construction of p. Moreover, since e(j) ∈ T, the definition of T guarantees that D contains the directed edge e(j) → p(e(j)). Hence π witnesses the existential condition in the definition of the matching sign.
uses
if_pos,if_neghave 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⟩) := by refine ⟨π, fun j hj => ?_⟩ have h0 : π ⟨2 * j, by omega⟩ = e ⟨j, by omega⟩ := by show f ⟨2 * j, by omega⟩ = _ simp only [f] rw [if_pos (by simp)] congr 1; ext; simp have h1 : π ⟨2 * j + 1, hj⟩ = p (e ⟨j, by omega⟩) := by show f ⟨2 * j + 1, hj⟩ = _ simp only [f] rw [if_neg (by omega)] congr 2; ext; simp only; omega rw [h0, h1] refine ⟨hp _, ?_⟩ have := he_mem ⟨j, by omega⟩ simpa [hT] using this
The value of orientation_perfect_matching_sign D M is either 1 or -1.
Unfolding orientation_perfect_matching_sign, the witness π validates the existential condition, triggering the positive branch of the definition and reducing the value to the sign of the permutation. Since the sign of a permutation is an integer unit, and the only units in ℤ are 1 and -1, the sign is either 1 or -1.
uses
dif_pos,Int.units_eq_one_orunfold orientation_perfect_matching_sign rw [dif_pos hπ] rcases Int.units_eq_one_or (Equiv.Perm.sign hπ.choose) with h | h <;> rw [h] <;> simp
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- Conjunction with True simplifies to the proposition itself.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_image.mp- If an element belongs to the image of a set under a function, it is the image of some element in that set.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to either set.
Finset.mem_image- An element is in the image of a set under a function if and only if it is the image of some element in the set.
iff_true- An equivalence between a proposition and True simplifies to the proposition itself.
Or.inl- A proof of the left disjunct proves a disjunction.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ- The cardinality of the universal finset is the cardinality of the underlying finite type.
Fintype.card_fin- The type Fin n has cardinality n.
Finset.card_image_of_injective- An injective map preserves the cardinality of a finite set under image.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
congrArg- Applying a function to equal arguments yields equal results.
Fin.val- The natural number value of an element of Fin n.
Equiv.ofBijective- A bijective map between two types yields an equivalence between them.
Finite.injective_iff_bijective.mp- An injective map from a finite type to itself is bijective.
if_pos- If the condition holds, an if-then-else expression evaluates to the then-branch.
if_neg- If the condition fails, an if-then-else expression evaluates to the else-branch.
dif_pos- A dependent if-then-else evaluates to its first branch when given a proof of the condition.
Int.units_eq_one_or- Every unit of the integers is either 1 or -1.
- The definition of orientation_perfect_matching_sign uses the axiom of choice to select a permutation satisfying the matching-orientation condition; this proof constructs an explicit witness π from the partition T to discharge the existential condition.
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_perfect_matching_sign_eq_one_or_neg_one {n : ℕ} (G : SimpleGraph (Fin n)) (D : Digraph (Fin n)) (hD : is_graph_orientation G D) (M : G.Subgraph) (hM : M.IsPerfectMatching) : orientation_perfect_matching_sign D M = 1 ∨ orientation_perfect_matching_sign D M = -1 := by classical -- the partner map have hex : ∀ v, ∃! w, M.Adj v w := fun v => hM.1 (hM.2 v) choose p hp huniq using hex have hpp : ∀ v, p (p v) = v := fun v => (huniq (p v) v (hp v).symm).symm have hpinj : Function.Injective p := fun a b h => by rw [← hpp a, h, hpp b] set T : Finset (Fin n) := Finset.univ.filter (fun v => D.Adj v (p v)) with hT have hxor : ∀ v, v ∈ T ↔ p v ∉ T := by intro v have hG : G.Adj v (p v) := M.adj_sub (hp v) have h1 := (hD.1 v (p v)).mpr hG have h2 := hD.2 v (p v) simp only [hT, Finset.mem_filter, Finset.mem_univ, true_and, hpp] tauto have hcard : 2 * T.card = n := by have hdisj : Disjoint T (T.image p) := by rw [Finset.disjoint_left] intro a ha hb obtain ⟨b, hbT, rfl⟩ := Finset.mem_image.mp hb exact ((hxor b).mp hbT) ha have hunion : T ∪ T.image p = Finset.univ := by ext v simp only [Finset.mem_union, Finset.mem_image, Finset.mem_univ, iff_true] by_cases hv : v ∈ T · exact Or.inl hv · right; exact ⟨p v, (hxor (p v)).mpr (by rw [hpp]; exact hv), hpp v⟩ have := Finset.card_union_of_disjoint hdisj rw [hunion, Finset.card_univ, Fintype.card_fin, Finset.card_image_of_injective _ hpinj] at this omega set m := T.card with hm let e : Fin m → Fin n := fun i => (T.equivFin.symm i : Fin n) have he_mem : ∀ i, e i ∈ T := fun i => (T.equivFin.symm i).2 have he_inj : Function.Injective e := fun a b h => T.equivFin.symm.injective (Subtype.ext h) let f : Fin n → Fin n := fun i => if i.val % 2 = 0 then e ⟨i.val / 2, by omega⟩ else p (e ⟨i.val / 2, by omega⟩) have hf_inj : Function.Injective f := by intro a b hab simp only [f] at hab split_ifs at hab with ha hb hb · have := congrArg Fin.val (he_inj hab); simp at this; ext; omega · exact absurd (hab ▸ he_mem _) ((hxor _).mp (he_mem _)) · exact absurd (hab.symm ▸ he_mem _) ((hxor _).mp (he_mem _)) · have := congrArg Fin.val (he_inj (hpinj hab)); simp at this; ext; omega let π : Equiv.Perm (Fin n) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf_inj) have 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⟩) := by refine ⟨π, fun j hj => ?_⟩ have h0 : π ⟨2 * j, by omega⟩ = e ⟨j, by omega⟩ := by show f ⟨2 * j, by omega⟩ = _ simp only [f] rw [if_pos (by simp)] congr 1; ext; simp have h1 : π ⟨2 * j + 1, hj⟩ = p (e ⟨j, by omega⟩) := by show f ⟨2 * j + 1, hj⟩ = _ simp only [f] rw [if_neg (by omega)] congr 2; ext; simp only; omega rw [h0, h1] refine ⟨hp _, ?_⟩ have := he_mem ⟨j, by omega⟩ simpa [hT] using this unfold orientation_perfect_matching_sign rw [dif_pos hπ] rcases Int.units_eq_one_or (Equiv.Perm.sign hπ.choose) with h | h <;> rw [h] <;> simp