Title: The Replication Conjecture
| Speaker: | Ahmad Abdi |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract: In 1972, Lovasz proved a key lemma that was the piece of the puzzle Fulkerson missed to prove the weak perfect graph theorem. This important lemma, called the Duplication Lemma, simply states that vertex duplication preserves graph perfection.
If we view graph perfection as a property of the associated set packing linear program, we see that the Duplication Lemma explains when this program is totally dual integral. Set packing and set covering programs are two sides of the same coin, so why not try and understand when the set covering program is totally dual integral in a similar fashion? In 1993, Conforti and Cornuejols formulated the so-called Replication Conjecture which states in the world of clutters, the associated combinatorial object, that vertex replication preserves the packing property.
In this talk, I will present some tools that will be helpful in tackling this conjecture. The upshot is to take advantage of the fact that clutters with the packing property exclude delta minors, as well as some other small minors.
Joint work with G. Cornuejols and K. Pashkovich.