Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes

This note illustrates the limitations of the hyperplane separation bound, a non-combinatorial lower bound on the extension complexity of a polytope. Most notably, this bounding technique is used by Rothvo{\ss} (J ACM 64.6:41, 2017) to establish an exponential lower bound for the perfect matching polytope. We point out that the technique is sensitive to the particular choice of slack matrix. For the \textit{canonical} slack matrices of the spanning tree polytope and the completion time polytope, we show that the lower bounds produced by the hyperplane separation method are trivial.