  In this paper we consider certain closed subvarieties of the flag variety,
known as Hessenberg varieties. We prove that Hessenberg varieties corresponding
to nilpotent elements which are regular in a Levi factor are paved by affines.
We provide a partial reduction from paving Hessenberg varieties for arbitrary
elements to paving those corresponding to nilpotent elements. As a consequence,
we generalize results of Tymoczko asserting that Hessenberg varieties for
regular nilpotent and arbitrary elements of \mathfrak{gl}_n(\C) are paved by
affines. For example, our results prove that any Hessenberg variety
corresponding to a regular element is paved by affines. As a corollary, in all
these cases the Hessenberg variety has no odd dimensional cohomology.
