# Incidence algebra

A

partially ordered set is

*locally finite* precisely if every closed

interval [

*a, b*] within it is

finite. For every locally finite poset and every

field of

scalars there is an

**incidence algebra**, an

associative algebra defined as follows. The members of the incidence algebra are the

functions *f* assigning to each interval [

*a, b*] a scalar

*f*(

*a*,

*b*). On this underlying set one defines addition and scalar multiplication pointwise, and "multiplication" in the incidence algebra is a

convolution defined by

The multiplicative identity element of the incidence algebra is

An incidence algebra is finite-dimensional if and only if the underlying

poset is finite.

The **ζ function** of an incidence algebra is the constant function ζ(*a, b*) = 1 for every interval [*a, b*]. One can show that that element is invertible in the incidence algebra (with respect to the convolution defined above). (Generally, a member *h* of the incidence algebra is invertible if and only if *h*(*x*, *x*) ≠ 0 for every *x*.) The multiplicative inverse of the ζ function is the **Möbius function** μ(*a, b*); every value of μ(*a, b*) is an integral multiple of 1 in the base field.

whenever *S* and *T* are finite subsets of *E* with *S* ⊆ *T*.

- The Möbius function on the set of non-negative integers with their usual order is

This corresponds to the sequence (1, −1, 0, 0, 0, ... ) of coefficients of the formal power series 1 − *z*, and the ζ function in this case corresponds to the sequence of coefficients (1, 1, 1, 1, ... ) of the formal power series (1 − *z*)^{−1} = 1 + z + z^{2} + z^{3} + .... The δ function in this incidence algebra similarly corresponds to the formal power series 1.

- Partially order the set of all partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. Then the Möbius function is

where *n* is the number of blocks in the finer partition σ, *r* is the number of blocks in the coarser partition τ, and *r*_{i} is the number of blocks of τ that contain exactly *i* blocks of σ.

## Euler characteristic

A poset is *bounded* if it has smallest and largest elements, which we call 0 and 1 respectively (not to be confused with the zero and the one of the base field, which, in this paragraph, we take to be **Q**). The **Euler characteristic** of a bounded finite poset is μ(0,1); it is always an integer. This concept is related to the classic Euler characteristic.

Incidence algebras of locally finite posets were treated in a number of papers of Gian-Carlo Rota beginning in 1964, and by many later combinatorialists. Rota's 1964 paper was:

*On the Foundations of Combinatorial Theory I: Theory of Möbius Functions*, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, volume 2, pages 340-368.