Minkowski decomposability of symmetric edge polytopes

Abstract

In this paper, we study the Minkowski decomposability of symmetric edge polytopes $P_G^{\pm }$ of a finite simple graph $G$ on vertex set $[n]$. More precisely, we give a complete characterization of graphs whose symmetric edge polytopes are Minkowski decomposable. We prove that $P_G^{\pm }$ is Minkowski decomposable if and only if $G$ is one of the three complete multipartite graphs: $K_n$, $K_{2,n-2}$, or $K_{1,1,n-2}$. In other words, if $G$ does not belong to these three families, then $P_G^{\pm }$ is Minkowski indecomposable.

11 pages, 1 figure, Lemma 4.2 has been revised