The techniques of linear programming provide powerful tools for studying matching problems in graph theory. Let G be a bidirected graph (a generalization of a directed graph, where each end of each edge has an independent direction) with a cost and an integral capacity associated to each edge and an integral demand b(v) at each vertex. We want a “flow” x(e) on each edge, which is nonnegative, does not exceed the capacity, is integer-valued, exactly meets the demand (the inflow to v, that is total inflow minus total outflow, equals b(v)), and has minimum cost. This is the “capacitated perfect b-matching problem” on bidirected graphs.

We can transform this into a linear programming problem by removing the integrality constraints and adding further restrictions involving odd subsets of the vertex set. Edmonds and Johnson's perfect b-matching theorem (1970) showed that the vertices of this new polytope are the minimum-cost, capacitated perfect b-matchings. This theorem can be proved by reducing it to the “perfect 1-matching problem”, which is the special case where every edge has two opposite arrows and all demands and capacities equal 1.

I will present a short proof of Edmonds' theorem on the perfect 1-matching polyhedron and a proof of the more general theorem on the perfect b-matching polyhedron for undirected graphs. Time permitting, I will present the proof of the general theorem on capacitated perfect b-matchings.

The talks are based on the papers “Reductions to 1-Matching Polyhedra” by Aráoz, Cunningham, Edmonds, and Green-Krótki (1983) and “Short Proofs on the Matching Polyhedron” by Schrijver (1983).

These talks constitute Mr. Joyce's admission-to-candidacy examination. The committee consists of Laura Anderson, Fernando Guzmán, and Thomas Zaslavsky (chair). All are welcome to attend.