Fast Möbius inversion in semimodular lattices and ER-labelable posets (Q311532): Difference between revisions

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. Let \((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. The 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. The 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.