Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A pop­u­lar method in com­bi­na­to­r­ial opti­miza­tion is to express poly­topes P, which may poten­tially have expo­nen­tially many facets, as solu­tions of lin­ear pro­grams that use few extra vari­ables to reduce the num­ber of con­straints down to a poly­no­mial. After two decades of stand­still, recent years have brought amaz­ing progress in show­ing lower bounds for the so called exten­sion complexity. How­ever, the cen­tral ques­tion in this field remained wide open: can the per­fect match­ing poly­tope be writ­ten as an LP with poly­no­mi­ally many constraints? We answer this ques­tion neg­a­tively. In fact, the exten­sion com­plex­ity of the per­fect match­ing poly­tope in a com­plete n-node graph is 2^Omega(n).

contact Matthias Koeppe