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 Spanning Tree polytope of a complete graph with n nodes. The best known lower bound is Omega(n(2)), the best known upper bound is O(n(3)).