On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope

Kaveh Khoshkhah, Dirk Oliver Theis

In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum S…