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

Abstract

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.
Published
2016-08-19
Article Number
P3.26