Advanced search
Start date
Betweenand

Conformal minors and Pfaffian orientations

Grant number: 18/04679-1
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): September 01, 2018
Effective date (End): June 30, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Orlando Lee
Grantee:Nishad Bharat Kothari
Home 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
(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. Web of Science Citations: 0.
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. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.