The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the matching polytope has exponential extension complexity, meaning that it cannot be represented by a polynomially sized linear program Rothvoss (2017). I think this is a very interesting result, as it illustrates the limitations of expressing problems as linear programs. My question: are there any other problems that are solvable in polynomial time but whose polytopes have exponential extension complexity?
I think the spanning tree polytope also falls under this category. Computing the minimum spanning tree is easy. However, we would require all the sub-tour elimination constraints (which is exponential in number of vertices) to represent the spanning tree polytope in 0-1 variables as a LP.
From the comments below, one can find a reference for a polynomial characterization of the spanning tree polytope. So my answer that the spanning tree has ``exponential extension complexity" is incorrect. I will however let this answer remain because I think not many people are aware of polynomial formulations for the spanning tree polytope. The edit is meant to notify people who read this post, not to overlook that fact.