Fractional perfect b-matching polytopes
by Dr Roger Behrend
Abstract: The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v is a prescribed positive number b_v for that vertex. General theorems which give the dimensions and characterize the vertices of such polytopes will be proved. Certain polytopes which correspond to particular cases of fractional perfect b-matching polytopes, and some of which are important in combinatorial optimization, will then be reviewed, and some standard results for these cases will be obtained using the previous, general theorems. These polytopes include the transportation, transshipment, Birkhoff and alternating sign matrix polytopes.
For More Information: contact: Mark Sorrell. email. email@example.com