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