The FKT algorithm counts perfect matchings in planar graphs using a single Pfaffian. For graphs embedded on an orientable surface of genus g, Galluccio–Loebl and Tesler showed that the perfect-matching polynomial can be expressed using at most 4^g Pfaffians. We prove that an exponential dependence on g is unavoidable: for every g>=1, there exists a graph of genus at most g whose perfect-matching polynomial requires at least (8/3)^g Pfaffians. We prove this by showing that expressing the permanent of a matrix as a linear combination of determinants of the same size signed matrices requires an exponential number of terms.
Bio: Prof. Ranveer Singh is an Associate Professor in the Department of Computer Science and Engineering at IIT Indore. He received his B.Tech and Ph.D. from IIT Jodhpur and was a postdoctoral fellow at the Technion–Israel Institute of Technology. His research interests include algebraic graph theory and the permanent vs determinant question.
