  We study flag enumeration in intervals in the Bruhat order on a Coxeter group
by means of a structural recursion on intervals in the Bruhat order. The
recursion gives the isomorphism type of a Bruhat interval in terms of smaller
intervals, using basic geometric operations which preserve PL sphericity and
have a simple effect on the cd-index. This leads to a new proof that Bruhat
intervals are PL spheres as well a recursive formula for the cd-index of a
Bruhat interval. This recursive formula is used to prove that the cd-indices of
Bruhat intervals span the space of cd-polynomials.
  The structural recursion leads to a conjecture that Bruhat spheres are
"smaller" than polytopes. More precisely, we conjecture that if one fixes the
lengths of x and y, then the cd-index of a certain dual stacked polytope is a
coefficientwise upper bound on the cd-indices of Bruhat intervals [x,y]. We
show that this upper bound would be tight by constructing Bruhat intervals
which are the face lattices of these dual stacked polytopes. As a weakening of
a special case of the conjecture, we show that the flag h-vectors of lower
Bruhat intervals are bounded above by the flag h-vectors of Boolean algebras
(i.e. simplices).
