  We introduce the simple extension complexity of a polytope P as the smallest
number of facets of any simple (i.e., non-degenerate in the sense of linear
programming) polytope which can be projected onto P. We devise a combinatorial
method to establish lower bounds on the simple extension complexity and show
for several polytopes that they have large simple extension complexities. These
examples include both the spanning tree and the perfect matching polytopes of
complete graphs, uncapacitated flow polytopes for non-trivially decomposable
directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex
numbers within a certain range. On our way to obtain the result on perfect
matching polytopes we generalize a result of Padberg and Rao's on the adjacency
structures of those polytopes. To complement the lower bounding techniques we
characterize in which cases known construction techniques yield simple
extensions.
