Abstract

We recently had a derandomization of the Isolation Lemma for perfect matchings in bipartite graphs and common base sets of two matroids. That is, a deterministic construction of an isolating weight assignment. The common idea in both the constructions is to work with their corresponding polytopes. In this talk, we present the approach in terms of general polytopes and describe sufficient conditions on the polytope for this approach to work. Finally, we argue that these conditions hold for bipartite matching polytope and common base set polytope.
 

Video Recording