2017/02/28 by Manuel Aprile, Aprile, Manuel, Yuri Faenza +7 · 1 citation
Computer Science · Engineering · Mathematics · #05Cxx #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #graph theory and CDMA systems #math.CO #msc:05Cxx
paper · pdf · doi:10.48550/arxiv.1702.08741
13 pages, 2 figures
openalex publication_date 2017/02/28 · arxiv created 2017/06/05 · arxiv updated 2017/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. It is easy to see that n \leqslant xc (STAB(G)) \leqslant n+m. We improve both of these bounds. For the upper bound, we show that xc (STAB(G)) is O((n2)/(log n)), which is an improvement when G has quadratically many edges. For the lower bound, we prove that xc (STAB(G)) is Ω(n log n) when G is the incidence graph of a finite projective plane. We also provide examples of 3-regular bipartite graphs G such that the edge vs stable set matrix of G has a fooling set of size |E(G)|.