Theorem 1.2 — non-Pfaffian iff some cut reversal is strongly connected
OpenPfaffianRecognition.Recognition.Supplement.theorem_1_2complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pfaffian
Let be a matching covered graph (connected, with at least one edge, every edge in a perfect matching) and let be an orientation of . For let be with every edge of the cut reversed. Then
where is Pfaffian when all perfect matchings of have the same sign under , and strongly connected means every vertex can be reached from every other by a directed path.
This structural characterization holds for every matching covered graph, bipartite or not; with the randomized Pfaffian-orientation test it yields a randomized algorithm for making a matching covered graph strongly connected by reversing a cut, a problem that is NP-complete for general digraphs.
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
- reading: matching covered (used, not defined, in the paper) → IsMatchingCovered: connected, at least one edge, every edge in some perfect matching; reason: the standard definition of [LP86]/[LM24] the paper cites; connectivity and an edge are part of it, and without them the statement fails on K1
Preamble
import Definitions.Def_PfaffianRecognition_Recognition_Supplement_cut_model
Formal statement
namespace PfaffianRecognition.Recognition.Supplement
open PfaffianRecognition.Recognition
/-- Theorem 1.2, p. 4 (proof pp. 12–14). For a matching covered graph `G` and an orientation `D`,
`D` is non-Pfaffian iff some cut reversal `D^X` is strongly connected. -/
theorem theorem_1_2 {N : ℕ} (G : SimpleGraph (Fin N)) (hG : IsMatchingCovered G)
(D : Orientation G) :
¬ IsPfaffianOrientation D ↔
∃ X : Set (Fin N), IsStronglyConnected (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), Theorem 1.2, p. 4 (proof pp. 12–14); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/858.pdf