Fast Möbius inversion in semimodular lattices and ER-labelable posets
type: Item
instance of: scholarly article
title: Fast Möbius inversion in semimodular lattices and ER-labelable posets
zbMATH Open document ID: 1377.06006
author: Petteri Kaski
author: Jukka Kohonen
author: Thomas Westerbäck
published in: The Electronic Journal of Combinatorics
publication date: 2016-09-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1603.03889
full work available at URL: v23i3p26
Mathematics Subject Classification ID: 06C10
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 6626790
zbMATH Keywords: Möbius inversion
zbMATH Keywords: semimodular lattice
zbMATH Keywords: ER-labelable poset
reviewed by: Tibor Katriňák
MaRDI profile type: Publication
arXiv ID: 1603.03889
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Fast Zeta Transforms for Lattices with Few Irreducibles
cites work: Shellable Nonpure Complexes and Posets. I
cites work: Q4331740
cites work: Q4198056
cites work: Lattice Theory: Foundation
cites work: Finding Efficient Circuits for Ensemble Computation
cites work: Computational aspects of the Mobius transformation of graphs
cites work: Fast Fourier transforms for finite inverse semigroups
cites work: Q5417641
cites work: Supersolvable lattices
cites work: Q3748279
cites work: Negation is Powerless for Boolean Slice Functions
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.
description: scientific article; zbMATH DE number 6626790