This material has been published in
Europ. J. Combin. 32 (2011), 1253-1281,
the only definitive repository of the content that has been
certified and accepted after peer review. Copyright and all rights therein
are retained by Elsevier B.V.
This material may not be copied or reposted
without explicit permission.
Gábor Hetyei and
The poset of bipartitions
Bipartitional relations were introduced by
Foata and Zeilberger in their characterization
of relations which give rise to equidistribution of the associated
inversion statistic and
major index. We consider the natural partial order on
bipartitional relations given by inclusion. We show that, with respect
this partial order, the bipartitional relations on a set of size n
form a graded lattice of rank 3n-2. Moreover, we prove that the order
complex of this lattice is homotopy equivalent to a sphere of
Each proper interval in this lattice has either a contractible order
complex, or it is isomorphic to the direct product of Boolean lattices
and smaller lattices of bipartitional relations.
As a consequence, we obtain that
the Möbius function of every interval is 0, 1, or -1.
The main tool in the proofs is discrete Morse theory as developed by
Forman, and an application of this theory to order complexes of graded
posets, designed by Babson and Hersh, in the extended form of
Hersh and Welker.
The following versions are available:
Back to Christian Krattenthaler's