  Let u and v be permutations on n letters, with u <= v in Bruhat order. A
Bruhat interval polytope Q_{u,v} is the convex hull of all permutation vectors
z = (z(1), z(2),...,z(n)) with u <= z <= v. Note that when u=e and v=w_0 are
the shortest and longest elements of the symmetric group, Q_{e,w_0} is the
classical permutohedron. Bruhat interval polytopes were studied recently by
Kodama and the second author, in the context of the Toda lattice and the moment
map on the flag variety.
  In this paper we study combinatorial aspects of Bruhat interval polytopes.
For example, we give an inequality description and a dimension formula for
Bruhat interval polytopes, and prove that every face of a Bruhat interval
polytope is a Bruhat interval polytope. A key tool in the proof of the latter
statement is a generalization of the well-known lifting property for Coxeter
groups. Motivated by the relationship between the lifting property and
R-polynomials, we also give a generalization of the standard recurrence for
R-polynomials. Finally, we define a more general class of polytopes called
Bruhat interval polytopes for G/P, which are moment map images of (closures of)
totally positive cells in the non-negative part of G/P, and are a special class
of Coxeter matroid polytopes. Using tools from total positivity and the
Gelfand-Serganova stratification, we show that the face of any Bruhat interval
polytope for G/P is again a Bruhat interval polytope for G/P.
