The Rectangle Covering Bound on the Extension Complexity of Small Cut Polytopes

The extension complexity of small cut polytopes on the complete graph is lower bounded by the rectangle covering bound. An investigation is done to find techniques of computing this number for small instances, using the symmetries of the cut polytope and linear programming formulations. The extension complexity is shown to be maximal for cut polytopes of complete graphs of up to 8 nodes.