Fooling Sets and the Spanning Tree Polytope
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 Spanning Tree problem on a complete graph with n nodes. The best known lower bound is \Omega(n^2), the best known upper bound is O(n^3). In this note … Read more