Given a sequence of objects and costs for triples of objects i, k and j that apply iff k occurs between i and j in the sequence, the betweenness problem asks for a minimum cost permutation of all objects. For many applications sparse models of betweenness problems are preferable. We generalize for sparse formulations the result that betweenness polytopes are faces of the cut polytope. Further we derive a combinatorial characterization of cuts in an associated graph that correspond to betweenness solutions. Finally we give computational results that exploit facets of sparse cut polytopes.