In Tom Leinster, The Euler Characteristic Of A Category, the author generalizes the notion of Möbius Inversion for posets to finite categories. This violates the principle of equivalence. A possible solution i found to that would be to consider essentially finite categories and apply the definitions given to the skeleton of such a category (the Möbius Inversion only exists for skeletal categories anyway according to the text). Since the definition of mobius inversion ignores compositions of morphisms, the author remarks:

The definitions above could be made for directed graphs rather than categories, since they do not refer to composition. However, this generality seems to be inappropriate. For example, the definition of Möbius inversion will lead to a definition of Euler characteristic, and if we use graphs rather than categories then we obtain something other than ‘vertices minus edges’. Proposition 2.10 clarifies this point. (...)

Proposition 2.10 Let G be a finite circuit-free directed graph. Then $\chi(F(G))$ is defined and equal to $|G_0|-|G_1|$.

Here $G_0$ and $G_1$ are the sets of vertices and edges respectively, and $F(G)$ is the free category on $G$. I don't understand the authors explanation for why to define this for finite skeletal categories instead of finite circuit-free directed graphs, nor how Proposition 2.10 relates to that. It seems inappropriate to me to define it for categories since this notion is not preserved for equivalence of categories, but it is preserved for isomorphisms of graphs. Am i missing something?


1 Answer 1


The formula for Mobius inversion of Theorem 1.4. holds more generally for a finite directed graph with the property that each of its circuits consists of edges from a vertex to itself (i.e. each circuit is a bouquet). Moreover, such graphs have Mobius inversion if and only if each vertex has at least one loop (see below for a proof). Similarly, the formula of Corollary 1.5. holds for such graphs that have unique loops at each vertex.

In particular, a circuit-free directed graph has no Mobius inversion.

The point of Proposition 2.10 is that nevertheless the category freely generated by a circuit-free finite directed graph does have Mobius inversion, hence an Euler characteristic, and that the Euler characteristic of the freely generated category agrees with the classical Euler characteristic as alternating sum of vertices and edges.

What's happening is this. On the one hand, the general definition of Mobius inversion makes sense for an arbitrary graph and does not rely on a notion of composition of edges (e.g. one given by a category). On the other hand, the formula of Theorem 1.4. expresses Mobius inversion in terms of paths on the graph. Consequently, since a category structure imposes a composition function from paths to edges, the Mobius inversion formula may become simpler for certain categories (e.g. as in Proposition 2.10).

Finally, note that the free reflexive graph generated by a circuit-free directed graph also has Mobius inversion given by the same formula as Theorem 1.4/Corollary 1.5. The corresponding Euler characteristic is, however, different unless there are no paths of length $2$ in the original graph, i.e. unless the freely generated reflexive graph is also the freely generated category. Since historically the alternating sum of vertices and edges has been an important topological invariant of graphs, this suggests that the Euler characteristic (and hence Mobius inversions if they exist) of categories (as graphs that underlie categories) rather than of graphs that don't underlie categories is a more immediate generalization of the classical notion.

Let $Z$ be the matrix whose entries are the number of edges between vertices. Using cycle notation for permutations, we see that each term of the permutation formula for the determinant is the number of decompositions of the graph into disjoint circuits of a particular cycle type, with sign specified by the parity of the lenghts of the circuits. If the only circuits consist of loops, all terms except the product of diagonal entries are necessarily zero. In that caes the matrix is invertible, i.e. the graph has Mobius inversion, if and only if each vertex has at least one loop.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .