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

MaRDI QIDQ311532zbMATH OpenFDO

Authors Petteri Kaski, Jukka Kohonen, Thomas Westerbäck

Publication date 13 September 2016

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

Full work available at URL https://arxiv.org/abs/1603.03889, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p26

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

zbMATH Keywords

ER-labelable posetMöbius inversionsemimodular lattice

Mathematics Subject Classification ID

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

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.

Review text

Fast methods for computing both zeta and Möbius transformations in finite posets or lattices are important for many algorithms of combinatorial nature. Generally, the authors seek to minimize the length of the programs.NEWLINENEWLINELet \((P;\leq)\) be a finite poset and let \(f:P\rightarrow A\) be a map to an abelian group \(A.\) The \textit{zeta transformation} of \(f\) is the function \(g:P\rightarrow A\) such that for all \(y\in P,\) \(g(y)=\sum(f(x): x\leq y)\) is true. For a given poset, the computation from \(f\) to its zeta transformation \(g\) can be represented as a \textit{straigt-line program}, which means that a sequence of elementary pairwise arithmetic operations can be executed in turn, without loops or conditional statements. Since the zeta transformation is always invertible, the authors construct a short straight-line program also for the inverse transformation, called the Möbius transformation.NEWLINENEWLINEThe complexity of the given poset is characterized by three quantities: the number of elements \(v=|P|,\) the number of join-irreducible elements \(n=|I|\) and the number of edges \(e=|E|\) of Hasse diagram of \(P.\) In addition to this, an \textit{edge labeling} \(\lambda:E\rightarrow Z\), or labeling with \textit{rising chains}, can be given.NEWLINENEWLINEThe authors present four new algorithms for fast zeta and Möbius transformations. More precisely: (1) In a semimodular lattice with \(e\) edges, the join irreducible elements can be ordered so that Algorithm 1 (for zeta transformation) generates exactly \(e\) additions. Algorithm 2 (for Möbius transformation) is similar. Subtraction replaces the addition. (2) In an ER-labelable poset that has \(e\) edges, the zeta transformation can be computed in \(e\) additions and the Möbius transformation in \(e\) subtractions.

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

Cites work

• A space-time tradeoff for permutation problems
• Computational aspects of the Mobius transformation of graphs
• Fast Fourier transforms for finite inverse semigroups
• Fast Zeta Transforms for Lattices with Few Irreducibles
• Finding efficient circuits for ensemble computation
• Fourier meets M\"{o}bius: fast subset convolution
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Lattice Theory: Foundation
• Negation is Powerless for Boolean Slice Functions
• Shellable Nonpure Complexes and Posets. I
• Supersolvable lattices

Cited in

(5)

• Focal points and their implications for Möbius transforms and Dempster-Shafer theory
• Efficient Möbius transformations and their applications to D-S theory
• The lattice of arithmetic progressions
• Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction
• Fast zeta transforms for lattices with few irreducibles

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)