Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Total dual integrality and perfect graphsOptimization
|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.