Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Total dual integrality and perfect graphs


Speaker: Edwin O'shea, Univ. of Washington
Location: 2112 MSB
Start time: Fri, Jan 27 2006, 2:10PM

Many problems in combinatorial optimization can be expressed as detecting total dual integrality (TDI) in a 'non-generic' system of linear inequalities. One such case is the weak perfect graph theorem (WPGT) of Lovasz. We will present various ways for detecting TDI in a non-generic system by studying secondary fans and Groebner bases of toric ideals. When coupled with computational algebra packages, this understanding provides an experimentally feasible tool for investigating TDI in a whole host of scenarios. It also provides a new, Groebner basis proof of WPGT for chordal graphs. More generally, we will present an explicit polyhedral strengthening of WPGT. This is joint work with Andras Sebo.