Title: Extension complexity of stable set polytopes of bipartite graphs,
Abstract: 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)|$.