3:30 pm, Seminar Hall Two unsolved problems: Birkhoff–von Neumann graphs and PMcompact graphs Nishad Kothari Institute of Computing University of Campinas (UNICAMP), Brazil. 110219 Abstract A wellstudied object in combinatorial optimization is the perfect matching polytope of a graph G — the convex hull of the incidence vectors of all perfect matchings of G. In any such investigation, one may assume that G is matching covered — that is, G is a connected graph (on at least two vertices) and each edge of G lies in some perfect matching. A graph G is Birkhoff–von Neumann if its perfect matching polytope is characterized solely by nonnegativity and degree constraints. A result of Balas (1981) implies that G is Birkhoff–von Neumann if and only if G does not contain a pair of vertexdisjoint odd cycles (C1, C2) such that G − V(C1) − V(C2) has a perfect matching. It follows immediately that the corresponding decision problem is in coNP. However, it is not known to be in NP. The problem is in P if the input graph is planar — due to a result of Carvalho, Lucchesi and Murty (2004). More recently, in a joint work with these three authors, we have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is ‘prismfree’. The combinatorial diameter of a polytope is the diameter of its 1skeleton graph. A graph G is PMcompact if the combinatorial diameter of its perfect matching polytope equals one. A result of Chv'atal (1975) implies that G is PMcompact if and only if G does not contain a pair of vertexdisjoint even cycles (C1, C2) such that G − V(C1) − V(C2) has a perfect matching. Once again the corresponding decision problem is in coN P, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is ‘nearbipartite’— due to results of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013). Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the “intersection” of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff–von Neumann as well as PMcompact. Thus the corresponding decision problem is in P. I will discuss the two problems, and our recent results mentioned above. The talk will be mostly selfcontained. I will assume only basic knowledge of graph theory. I will perhaps not present any lengthy proofs. For more details, see: https://arxiv.org/abs/1807.07339 and https://epubs.siam.org/doi/abs/10.1137/17M1138704.
