| Department of Mathematical Sciences Colloquium Series |
|
 |
|
 |
|
University of Montana
3:10 p.m. in Math 103
4:00 p.m. Refreshments in Math Lounge 109
|
 |
|
||||||
|
|
||||||
|
Mark Kayll University of Montana |
||||||
| In 1965, at the height of Beatlemania, Jack Edmonds published his groundbreaking characterization of the perfect matching polytope of a graph G = (V,E), i.e., the convex hull P of the characteristic vectors of the perfect matchings in G. Edmonds described P polyhedrally as the set of nonnegative vectors in ℝE satisfying two families of constraints: 'saturation' and 'blossom'. Graphs for which the latter constraints are implied by the former are now called non-Edmonds graphs. As it turns out, this graph class interacts interestingly with more familiar classes. For example, bipartite graphs are non-Edmonds, and this assertion is equivalent to the Birkhoff–von Neumann Theorem on doubly-stochastic matrices. This talk will explore several connections of this nature and will be accessible to non-experts. | ||||||
|
Monday, 4 February 2013 3:10 p.m. in Math 103 4:00 p.m. Refreshments in Math Lounge 109 |
||||||
|
||||||
|
||||||