BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/941
DTSTAMP:20230914T125944Z
SUMMARY:Two unsolved problems: Birkhoff-von Neumann graphs and PM-compact g
raphs
DESCRIPTION:Speaker: Nishad Kothari (The University of Campinas\nSP\, Brazi
l)\n\nAbstract: \nAbstract: A well-studied object in combinatorial optim
ization is the perfect matching polytope PMP(G) of a graph G - the convex
hull of the incidence vectors of all perfect matchings of G. A graph G is
Birkhoff-von Neumann if PMP(G) is characterized solely by non-negativity
and degree constraints\, and G is PM-compact if the combinatorial diamete
r of PMP(G) equals one. Chvatal (1973) provided a graph-theoretical co -
NP characterization of PM-compact graphs\, and Balas (1981) provided one f
or Birkhoff-von Neumann graphs\; there is a striking similarity between t
heir characterizations. However\, so far\, we do not know of any NP chara
cterization for either of these graph classes.\n\nRecently\, in a joint wo
rk with Marcelo H. de Carvalho\, Xiumei Wang and Yixun Lin\, we considere
d the "intersection" of these graph classes. We give a complete characteri
zation of graphs that are Birkhoff-von Neumann as well as PM-compact. Cons
equently\, the corresponding decision problem is in P. Earlier\, in a joi
nt work with Claudio L. Lucchesi\, Marcelo H. de Carvalho and U. S. R. Mu
rty\, we showed that the problem of deciding whether a graph G is Birkhof
f-von Neumann is equivalent to the seemingly unrelated problem of deciding
whether G is `prism-free'.\n\nI will discuss the two problems\, and our r
ecent results mentioned above. The talk will be mostly self-contained. I
will assume only basic knowledge of graph theory. I will perhaps not prese
nt any lengthy proofs. For more details\, see: https://arxiv.org/abs/1807
.07339 and \nhttps://epubs.siam.org/doi/abs/10.1137/17M1138704.\n \n
URL:https://www.tcs.tifr.res.in/web/events/941
DTSTART;TZID=Asia/Kolkata:20190219T143000
DTEND;TZID=Asia/Kolkata:20190219T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR