Lemma 4.3 — reversing a cut preserves Pfaffianity
OpenPfaffianRecognition.Recognition.Supplement.lemma_4_3complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pfaffian
Let be a finite simple graph with a perfect matching, an orientation of and . Let be obtained from by reversing every edge with exactly one endpoint in . Then
The paper attributes this to [dCLM05]; it is used in the converse direction of Theorem 1.2.
Differences from the source:
- encoding: arbitrary finite simple graph G → SimpleGraph (Fin N) for every N, vertices in a fixed order; reason: every finite simple graph has such a labelling; no instance is removed
Preamble
import Definitions.Def_PfaffianRecognition_Recognition_Supplement_cut_model
Formal statement
namespace PfaffianRecognition.Recognition.Supplement
open PfaffianRecognition.Recognition
/-- Lemma 4.3, p. 12 ([dCLM05]). Reversing the edges of a cut preserves Pfaffianity. -/
theorem lemma_4_3 {N : ℕ} {G : SimpleGraph (Fin N)}
(hG : ∃ F : Finset G.edgeSet, MulmuleyVV.Matching.IsPerfectMatchingEdges G F)
(D : Orientation G) (X : Set (Fin N)) :
IsPfaffianOrientation D ↔ IsPfaffianOrientation (cutReversal D X) := by sorry
end PfaffianRecognition.Recognition.Supplement
Source
Priyanshu Pant, Ranveer Singh, Pfaffian Recognition is in coRP, STOC 2027 submission #858 (October 2026), Lemma 4.3, p. 12; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/858.pdf