The extension complexity $\mathsf{ 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 $\mathsf{ STAB}(G)$ be the convex hull of the stable sets of $G$. It is easy to see that $n \leqslant \mathsf{ xc} (\mathsf{ STAB}(G)) \leqslant n+m$. We improve both of these bounds. For the upper bound, we show that $\mathsf{ xc} (\mathsf{ STAB}(G))$ is $O(\frac{ n^2}{ \log n})$, which is an improvement when $G$ has quadratically many edges. For the lower bound, we prove that $\mathsf{ xc} (\mathsf{ STAB}(G))$ is $\Omega(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)|$.
Categories: cs.DM math.CO