Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes

The hyperplane separation bound is a lower bound on the extension complexity of a polytope. It is the main tool in Rothvoß's proof of an exponential bound for the matching polytope (Rothvoß, 2017). We show that the technique is sensitive to the choice of slack matrix and does not improve upon the best known lower bounds for spanning tree and completion time polytopes when applied to their canonical slack matrices. Stronger bounds may be obtained by appropriate rescalings and redundancy.