Combinatorial Optimization Reading Group - David Aleman

Title: Subgraph Polytopes and Independence Polytopes of Count Matroids

Abstract: Given a graph G=(V,E), the subgraph polytope of G is defined as the convex hull of the characteristic vector of the pairs (S,F) such that S is a non-empty subset of vertices and F is a set of edges contained in the induced subgraph G[S]. In this talk we describe a relationship between this polytope and the spanning forest polytope of G, and then show that these two polytopes can be used to provide a polynomial size extended formulation for the independence polytope of count matroids. This talk is based on a paper by M. Conforti, V. Kaibel, M. Walter and S. Weltge from 2015.