C&O Reading Group - Nishad Kothari

Monday, March 7, 2016 4:30 pm - 4:30 pm EST (GMT -05:00)

Title: The perfect matching polytope and solid graphs

Speaker: Nishad Kothari
Affiliation: University of Waterloo
Room: MC 6486

Abstract:The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of its perfect matchings. Edmonds (1965) gave an exact characterization of the perfect matching polytope; in particular, he showed that a vector belongs to this polytope if and only if it satisfies (1) non-negativity constraints, (2) degree constraints and (3) odd set constraints. Carvalho, Lucchesi and Murty (2004) characterized graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. It is well-known that bipartite graphs have this property. I will discuss their result and some related work.

Reference:
http://www.sciencedirect.com/science/article/pii/S0095895604000772

Door will open at 4:30pm. As usual we will have 15 mins for
socializing and for eating pizza before the talk starts (at 4:45pm sharp).

For more information about our reading group, please visit our webpage
http://www.math.uwaterloo.ca/~hwolkowi/reading.htm