Fast Möbius Inversion in Semimodular Lattices and ER-labelable Posets

  • Petteri Kaski
  • Jukka Kohonen
  • Thomas Westerbäck
Keywords: Möbius transform, Zeta transform, Lattices, Ensemble computation


We consider the problem of fast zeta and Möbius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and Möbius transforms can be computed in $O(e)$ elementary arithmetic operations, where $e$ denotes the size of the covering relation. We show that this family is exactly that of geometric lattices. We also extend the algorithms so that they work in $e$ operations for all semimodular lattices, including chains and divisor lattices. Finally, for both transforms, we provide a more general algorithm that works in $e$ operations for all ER-labelable posets.
Article Number