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

Petteri Kaski, Jukka Kohonen, Thomas Westerbäck

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.

Keywords


Möbius transform; Zeta transform; Lattices; Ensemble computation

Full Text: PDF