School Seminars and Colloquia

Fractional perfect b-matching polytopes

Tuesday Seminar

by Dr Roger Behrend


Institution: Cardiff University, UK
Date: Tue 17th May 2011
Time: 1:00 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

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. msorrell@unimelb.edu.au