Fast Möbius inversion in semimodular lattices and ER-labelable posets

zbMATH Open1377.06006arXiv1603.03889MaRDI QIDQ311532FDOQ311532

Petteri Kaski, Thomas Westerbäck, Jukka Kohonen

Publication date: 13 September 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the problem of fast zeta and M"obius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and M"obius 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 R-labelable posets and their non-graded generalization, which we call U-labelable.

Full work available at URL: https://arxiv.org/abs/1603.03889

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Fast zeta transforms for lattices with few irreducibles
• Fast Zeta Transforms for Lattices with Few Irreducibles
• On lattices with Möbius function \(\pm 1,0\)
• Möbius functions of lattices
• Computational aspects of the Mobius transformation of graphs

zbMATH Keywords

semimodular latticeER-labelable posetMöbius inversion

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Combinatorics of partially ordered sets (06A07) Semimodular lattices, geometric lattices (06C10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Lattice Theory: Foundation
• Title not available (Why is that?)
• Supersolvable lattices
• Finding Efficient Circuits for Ensemble Computation
• Shellable Nonpure Complexes and Posets. I
• Fourier meets M\"{o}bius: fast subset convolution
• Computational aspects of the Mobius transformation of graphs
• Negation is Powerless for Boolean Slice Functions
• Fast Zeta Transforms for Lattices with Few Irreducibles
• Title not available (Why is that?)
• Fast Fourier transforms for finite inverse semigroups

Cited In (4)

• Focal points and their implications for Möbius transforms and Dempster-Shafer theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient Möbius Transformations and Their Applications to D-S Theory

This page was built for publication: Fast Möbius inversion in semimodular lattices and ER-labelable posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311532)