Combinatorial Optimization Reading Group - David Aleman

Friday, March 24, 2023 12:00 pm - 12:00 pm EDT (GMT -04:00)

Title: Subgraph Polytopes and Independence Polytopes of Count Matroids

Speaker: David Aleman
Affiliation: University of Waterloo
Location: MC 6029

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.