Conformal minors and Pfaffian orientations

• Grant number: 18/04679-1
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: September 01, 2018
• End date: June 30, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: Nishad Bharat Kothari
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

The notion of Pfaffian orientations was introduced by Kasteleyn (1963) to solve the dimer problemin statistical mechanics. Its significance arises from the fact that if a graph admits a Pfaffian orientation then the number of its perfect matchings can be computed in polynomial-time. In general, the problem of deciding whether a graph admits a Pfaffian orientation is not known to be polynomial-time solvable, and is of great interest to theoretical computer scientists. The notion of Pfaffian orientations is intrinsically related to the graph theoretic concept of conformal minors. Little (1975) showed that a bipartite graph $G$ is Pfaffian if and only if$G$ does not contain $K{3,3}$ as a conformal minor (that is, if and only if $G$ is $K_{3,3}$-free). A structural characterization of $K{3,3}$-free bipartite graphs was obtained by McCuaig (2004), and independently by Robertson, Seymour and Thomas (1999), and this yields a polynomial-time algorithm for deciding whether a bipartite graph is Pfaffian or not. Miranda (2006) and Whalen (2014) found alternative proofs. In a joint work with Murty (2016), we characterized $K_4$-free planar graphs. The problem of characterizing $K_4$-free nonplanar graphs is much harder, and we have evidence to believe that it is related to the problem of characterizing Pfaffian graphs. We have specific conjectures that are supported by computational experiments, and we intend to resolve as many of these conjectures as possible. (AU)

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

LU, FULIANG; KOTHARI, NISHAD; FENG, XING; ZHANG, LIANZHU. Equivalence classes in matching covered graphs. DISCRETE MATHEMATICS, v. 343, n. 8, AUG 2020. (18/04679-1)

KOTHARI, NISHAD; DE CARVALHO, MARCELO H.; LUCCHESI, CLAUDIO L.; LITTLE, CHARLES H. C.. On essentially 4-edge-connected cubic bricks. ELECTRONIC JOURNAL OF COMBINATORICS, v. 27, n. 1, JAN 24 2020. (18/04679-1)

FABRES, PHELIPE A.; KOTHARI, NISHAD; DE CARVALHO, MARCELO H.. Minimal braces. JOURNAL OF GRAPH THEORY, v. 96, n. 4, p. 490-509, MAR 2021. (18/04679-1)

DE CARVALHO, MARCELO H.; KOTHARI, NISHAD; WANG, XIUMEI; LIN, YIXUN. BIRKHOFF VON NEUMANN GRAPHS THAT ARE PM-COMPACT. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 34, n. 3, p. 22-pg., 2020-01-01. (18/04679-1)