BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/810
DTSTAMP:20230914T125939Z
SUMMARY:Pfaffian Orientations and Conformal Minors
DESCRIPTION:Speaker: Nishad Kothari (Univ. of Waterloo & Univ. of Vienna\n2
00 University Ave W\nWaterloo\, ON N2L 3G1\nCanada\n )\n\nAbstract: \nVal
iant (1979) showed that unless $P = NP$\, there is no polynomial-time algo
rithm to compute the number of perfect matchings of a given graph --- even
if the input graph is bipartite. Earlier\, the physicist Kasteleyn (1963)
introduced the notion of a special type of orientation of a graph\, and h
e referred to graphs that admit such an orientation as Pfaffian graphs. Ka
steleyn showed that the number of perfect matchings is easy to compute if
the input graph is Pfaffian\, and proved that every planar graph is Pfaffi
an. The smallest non-Pfaffian graph is $K_{3\,3}$. In general\, the proble
m of deciding whether a given graph is Pfaffian is not known to be in $P$.
\n\nSpecial types of minors\, known as conformal minors\, play a key role
in the theory of Pfaffian orientations. In particular\, a graph is Pfaffia
n if and only if each of its conformal minors is Pfaffian. Little (1975) p
roved that a bipartite graph $G$ is Pfaffian if and only if $G$ does not c
ontain $K_{3\,3}$ as a conformal minor (or\, in other words\, if and only
if $G$ is $K_{3\,3}$-free)\; this places the problem of deciding whether a
bipartite graph is Pfaffian in co-NP. Several years later\, a structural
characterization of $K_{3\,3}$-free bipartite graphs was obtained by McCua
ig\, Robertson\, Seymour and Thomas (STOC 1997)\, and this led to a polyno
mial-time algorithm for deciding whether a given bipartite graph is Pfaffi
an. No such algorithm is known for general graphs.\n\nNorine and Thomas (2
008) showed that\, unlike the bipartite case\, it is not possible to chara
cterize all Pfaffian graphs by excluding a finite number of graphs as conf
ormal minors. In light of everything that has been done so far\, it would
be interesting to even identify rich classes of Pfaffian graphs (that are
nonplanar and nonbipartite).\n\nInspired by a theorem of Lovasz (1983)\, w
e took on the task of characterizing graphs that do not contain $K_4$ as a
conformal minor --- that is\, $K_4$-free graphs. In a joint work with U.
S. R. Murty (Journal of Graph Theory 2016)\, we provided a structural char
acterization of planar $K_4$-free graphs. The problem of characterizing no
nplanar $K_4$-free graphs is much harder\, and we have evidence to believe
that it is related to the problem of recognizing Pfaffian graphs. In part
icular\, we conjecture that every graph that is $K_4$-free and $K_{3\,3}$-
free is also Pfaffian.\n
URL:https://www.tcs.tifr.res.in/web/events/810
DTSTART;TZID=Asia/Kolkata:20170922T160000
DTEND;TZID=Asia/Kolkata:20170922T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR