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