Euler Characteristic of a Category

October 11, 2006

Posted by David Corfield

After Baez and Dolan taught us about groupoid cardinality (p. 15), now Tom Leinster teaches us about the Euler characteristic of a category.

I wonder if anything further has been done about the former’s wonderfully wild idea that the Euler characteristic of the sphere, i.e., 2, should be the same as what they call its homotopy cardinality on the page mentioned above, defined as an alternating product of the orders of the homotopy groups of the sphere.

Posted at October 11, 2006 8:38 AM UTC

TrackBack URL for this Entry: http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/979

84 Comments & 4 Trackbacks

Re: Euler Characteristic of a Category

David wrote:

I wonder if anything further has been done…

No, not that I know of. However, Dan Christensen has been telling me some wonderful things about homotopy cardinality versus Euler characteristic. I’m too tired to retell these things now, but anyone curious about the general idea should look here:

John Baez, The mysteries of counting: Euler characteristic versus homotopy cardinality.

Lots of links… and I’ll have to add one to Tom’s new paper!

Does anyone have the energy to summarize Tom’s new paper? This is the place to do it!

Tom?

Posted by: John Baez on October 12, 2006 6:06 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

John wrote:

Does anyone have the energy to summarize Tom’s new paper?

The energy, but not quite the time. This is a summarized summary:

The Euler characteristic of a category is the sum of the entries of the inverse of the matrix of the cardinalities of the hom-sets.

More another time!

Tom

Posted by: Tom Leinster on October 12, 2006 7:05 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

I’m not sure we should be asking Tom to summarise his own paper, unless there’s an enlightening way to see what’s going on which is not included in it. I remember during a discussion of my book on the Foundations of Mathematics list, which was sparked off by someone reporting John’s review, feeling a wee bit annoyed being asked to summarise what I’d written by a person who felt he didn’t have time to read it. It didn’t stop him discussing the book though.

Perhaps it would be better to tease further thoughts out of Tom. Such as what prospects are there to extend the construction to categories with infinitely many isomorphism classes of object? Is there an obvious example of such a category where we already know what cardinality we’d like it to have, something like FinSet for Baez-Dolan, perhaps using all the kinds of wonderful trick appearing from p. 17 onwards of this? Are there any prospects for an extension to bicategories?

Posted by: David Corfield on October 13, 2006 8:04 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

David wrote:

I’m not sure we should be asking Tom to summarise his own paper […]

I take the point, and it’s true that I’ve already written the best 2-page summary I could manage: it’s the introduction to my paper. On the other hand, I feel so warmly towards you people that I’d happily write a shorter and chattier summary.

In fact, I wrote a shorter chattier summary for this blog last night, but having come into the office in order to post it here, I discover that I left it at home :-(

David wrote:

what prospects are there to extend the construction to categories with infinitely many isomorphism classes of object?

(Background: I only defined Euler characteristic for (some) finite categories.)

The only thoughts I’ve had about infinite categories are the obvious ones, so I didn’t bother including them in the paper. More specifically, what I do involves various finite sums, and of course you can try to interpret them in an infinite situation, and sometimes you get convergence and sometimes you don’t.

An important point is that no matter how much you try to relax the finiteness conditions, you always need to keep the condition that each hom-set is finite. This is because the whole approach depends on knowing what the cardinality of a finite set is.

In fact, if you have any monoidal category V and a notion of “cardinality” or “Euler characteristic” of objects of V, then you can define the Euler characteristic of a finite V-enriched category by mimicking the original case (V = FinSet) in the simplest possible way.

In particular, there’s an answer to David’s question:

Are there any prospects for an extension to bicategories?

Yes: take V = FinCat. And you can go all the way up the n-categorical ladder: see p.15 of my paper.

David wrote:

Is there an obvious example of such a category where we already know what cardinality we’d like it to have, something like FinSet for Baez-Dolan […] ?

Yes. If G is a finite directed graph and F(G) denotes the free category on G, we’d expect F(G) to have the same Euler characteristic as G (namely, no. of vertices minus no. of edges). This is proved in my paper when F(G) is finite. But it may be that F(G) is infinite, even though G is finite.

For instance, we’d expect the free monoid on n generators, regarded as a one-object category, to have Euler characteristic 1 - n.

We’d also expect the free group on n generators to have Euler characteristic 1 - n, since it has a bouquet of n circles as a classifying space.

Posted by: Tom Leinster on October 14, 2006 2:41 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

you always need to keep the condition that each hom-set is finite

I suppose there might be some scope in enriched categories to flout this condition. E.g., if you had $R^{n}$ worth of morphisms between 2 objects, you could take its Euler characteristic $(- 1)^{n}$ .

Posted by: David Corfield on October 15, 2006 11:54 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

David wrote:

if you had $R^{n}$ worth of morphisms between 2 objects, you could take its Euler characteristic $(- 1)^{n}$ .

Agreed. This is another example of the generalization to enriched categories that I mentioned in a previous comment. Here, we’d be enriching over some category of topological spaces.

Posted by: Tom Leinster on October 15, 2006 7:24 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

That would raise the problem of identical rows occurring in the matrix to be inverted, even in a skeletal category. E.g., if all Hom sets were finite dimensional complex vector spaces, all entries would be 1.

Posted by: David Corfield on October 18, 2006 2:40 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

True, but that’s only a “problem” in the sense that it prevents the category from having Mobius inversion. It doesn’t prevent it from having Euler characteristic, which is a weaker property.

Incidentally, if all your hom-sets are vector spaces (and composition is bilinear) then it might be more appropriate to interpret the “cardinality” of each hom-set as its dimension. (This is mentioned briefly on p.15.) For example, an n-dimensional k-algebra A, interpreted as a one-object category enriched in k-modules, would then have Euler characteristic 1/n. In particular, A might be the group algebra of a group G of order n; then A and G have the same Euler characteristic, which is nice.

Of course, it all depends on what you want to achieve.

Posted by: Tom Leinster on October 18, 2006 5:40 PM | Permalink | Reply to this

Summary.

Here is my summary:

There are previously known notions of Euler characteristic (or cardinality) for groupoids, posets, and digraphs, which are all fairly simple: * The Euler characteristic of a groupoid is the sum, over connected components, of the reciprocal of the order of the automorphism group. * The Euler characteristic of a poset is the number of chains in the poset, weighted (in the usual fashion) by the parity of the length of the chain. * The Euler characteristic of a digraph is the number of vertices minus the number of edges.

Tom has a definition of Euler characteristic of a category that simultaneously generalises these. (Groupoids and posets are categories in the obvious way; a digraph gives rise to a free category.) The definition is still a bit complicated (so I leave it to an appendix), and it’s still defined in too few cases. However, it has all the usual nice properties that one would expect for a generalisation of cardinality.

The paper also includes a few applications of the theory; for example, it’s related to Möbius inversion and the inclusion/exclusion principle.

Posted by: Toby Bartels on October 14, 2006 5:44 PM | Permalink | Reply to this

Appendix.

$MathML-enabled post (click for more details).$

Here is the definition:

Given objects a and b in the category, let $ζ_{b}^{a}$ be the number of morphisms from a to b. A weighting on the category is a function a ↦ k^a, assigning a rational number to each isomorphism class of objects, such that $\sum_{b} ζ_{b}^{a} k^{b} = 1$ for each object a. Similarly, a coweighting is a function a ↦ k_a such that $\sum_{a} k_{a} ζ_{b}^{a} = 1$ for each b.

Weightings and coweightings need not exist, nor be unique. However, it is a theorem that if a weighting and a coweighting both exist, then $\sum_{a} k_{a} = \sum_{b} k^{b} .$ This sum is the Euler characteristic of the category.

The proof of this theorem is immediate, by plugging in an appropriate expression for 1 and swapping the order of summation. However, because of this swap, it may not apply if there are infinitely many isomorphism classes of objects. Thus, Tom’s paper limits itself to finite categories.

(Tom: Please confirm!)

Posted by: Toby Bartels on October 14, 2006 6:11 PM | Permalink | Reply to this

Re: Appendix.

$MathML-enabled post (click for more details).$

Toby wrote:

(Tom: Please confirm!)

I do. Thanks!

I also agree with this (again from Toby):

The definition is still a bit complicated […] and it’s still defined in too few cases.

I’d like to remedy both these situations. Ideally, the slightly ad hoc definition that I gave could be replaced by some nice universal property, or at least something more conceptual.

I’ve tried to do this but not come up with anything great. All I can really offer is this: if you want the theorem (2.8) on the Euler characteristic of a fibred category to be true, you’re forced to define “weight” in the way that I do - for take $X$ to be representable.

To cure “defined in too few cases”, I think we need to move beyond the rational numbers. As I mentioned briefly at the end of the Introduction, I suspect that we should be looking for Euler characteristic valued in other rigs.

There seems to be a similar situation with Euler characteristic of topological spaces. Take the set $X = {0, 1 / 2, 1 / 4, 1 / 8, \dots}$ . This satisfies $X ≅ 1 + X$ , so you’d expect its Euler characteristic $x$ to satisfy $x = 1 + x$ . But this has no solutions in any non-trivial ring, so if you want $X$ to have an Euler characteristic you’d better move to some other rig.

Posted by: Tom Leinster on October 15, 2006 7:40 PM | Permalink | Reply to this

New rigs.

The nice thing about the rationals (or reals, for Baez–Dolan groupoid cardinality) is that they include all of the other rigs. But any rig containing the integers is a ring. (To be precise, any rig with a rig homomorphism from Z is a ring.) Since we can add and multiply any categories, we’d like to add and multiple their Euler characteristics, but then they need to belong to the same rig.

Posted by: Toby Bartels on October 17, 2006 11:04 PM | Permalink | Reply to this

Discrete Calculus

$MathML-enabled post (click for more details).$

I’m going to take the liberty to convert some of this stuff into the language of discrete calculus. For background, you can try (although maybe not advised) to read the paper Urs and I worked on together

Discrete Differential Geometry on Causal Graphs

Then, there is a much simpler paper I wrote separately where the goal was to write it so that even finance people (which includes more and more physicists these days) could understand

Financial Modeling Using Discrete Stochastic Calculus

In it, I give a brief review of discrete calculus on directed graphs and show how in different continuum limits, you can recover either exterior calculus or stochastic calculus.

The basic idea is that we have some directed graph $G$ , with nodes denoted by $e_{a}$ and an edge directed from $e_{a}$ to $e_{b}$ denoted by $e_{ab}$ . To keep things simple, I’ll assume the number of nodes is finite (or at least if they are infinite, then they are infinite in such a way that I do not need to worry about rearranging summations).

We can also introduce functionals, i.e. discrete differential forms, on nodes and directed edges with bases given by $e^{a}$ and $e^{ab}$ with contraction written as an integral, i.e.

(1)

\int_{e_{a}} e^{b} = δ_{a}^{b}

and

(2)

\int_{e_{ab}} e^{cd} = δ_{a}^{c} δ_{b}^{d} .

The vector space generated by $e^{a}$ is the space of discrete 0-forms $Ω^{0}$ so that an arbitrary discrete 0-form may be written as

(3)

f = \sum_{a} f_{a} e^{a} .

Similarly, the space of discrete 1-forms is generated by $e^{ab}$ so that an arbitrary discrete 1-form may be written as

(4)

α = \sum_{a \to b} α_{ab} e^{ab} .

I like to write contraction as an integral because we end up with intuitive looking things like

(5)

\int_{e_{a}} f = f_{a},

which is simply 0-dimensional integration (or evaluation at a point) and

(6)

\int_{e_{ab}} α = α_{ab}

which is simply 1-dimensional integration (or evaluation along an edge).

We have some simple multiplication rules

(7)

e^{a} e^{b} = δ^{ab} e^{a}

so that multiplication of 0-forms is what we would expect, e.g.

(8)

fg = \sum_{a} f_{a} g_{a} e^{a} .

The magic comes in when we define multiplication of a 0-form and a 1-form. This is done via the very intuitive rule

(9)

e^{a} e^{bc} = δ^{ab} e^{bc}

and

(10)

e^{ab} e^{c} = δ^{bc} e^{ab} .

Unless we start talking about 2-categories (which I hope we do), we will not need a multiplication rule for 1-forms, but it is as obvious as you would think.

I say this is intuitive because when we multiply a 0-form $f$ on the left of a directed (co)edge $e^{ab}$ we get

(11)

f e^{ab} = f (a) e^{ab},

i.e. multiplication picks out the value of the 0-form at the beginning of the edge. Similarly,

(12)

e^{ab} f = f (b) e^{ab},

i.e. multiplication on the right picks out the value of the 0-form at the end of the directed edge.

The important thing here is that clearly discrete 0-forms and discrete 1-forms do not commute. This has pretty mind numbing consequences and is how I managed to rope Urs into all this stuff :)

Next, let’s introduce what we called the “graph operator”

(13)

ζ = \sum_{a \to b} e^{ab} .

What Tom calls a weighting can also be thought of a 0-form $\vec{k}$ multiplying the graph operator on the right such that

(14)

\int_{G_{1}} ζ \vec{k} = 1,

where

(15)

G_{1} = \sum_{a \to b} e_{ab} .

Similarly, a coweighting can be thought of as a 0-form $\overset{\leftarrow}{k}$ multiplying the graph operator on the left such that

(16)

\int_{G_{1}} \overset{\leftarrow}{k} ζ = 1 .

Apparently, the claim is that when both $\vec{k}$ and $\overset{\leftarrow}{k}$ exist, then we have

(17)

\int_{G_{0}} \vec{k} = \int_{G_{0}} \overset{\leftarrow}{k} = χ (G),

where

(18)

G_{0} = \sum_{a} e_{a} .

I’m not sure that this change of perspective is helpful (I think it is), but I thought I would write it out just in case.

Another thing that comes to mind (this is basically another stream of consciousness) is that for some directed graphs, the discrete exterior derivative (or coboundary) can be expressed in terms of a commutator with the graph operator, i.e.

(19)

df = [ζ, f] .

Therefore, on such a directed graph we would have

(20)

ζ \vec{k} = \vec{k} ζ + d \vec{k}

and if the graph has no boundary than

(21)

\int_{G_{1}} ζ \vec{k} = \int_{G_{1}} \vec{k} ζ = 1 .

If these conditions are satisfied, we could actually have the weight equal to the coweight. Not sure if that is important, but thought I would point it out.

Now that I’ve converted to a language I better understand I’ll try to think about that formula John is after.

Posted by: Eric on October 21, 2006 6:38 AM | Permalink | Reply to this

Re: Discrete Calculus

$MathML-enabled post (click for more details).$

I warned you that I am almost always wrong :)

The conditions from Tom’s paper (as summarized by Toby) do not require the integrals over the entire graph. Rather, it should be

(1)

\int_{G_{1} e_{b}} ζ \vec{k} = \int_{e_{a} G_{1}} \overset{\leftarrow}{k} ζ = 1,

for all $a$ and $b$ , where

(2)

G_{1} e_{b} = \sum_{a} e_{ab}

is the sum of all edges incident onto $b$ and

(3)

e_{a} G_{1} = \sum_{b} e_{ab}

is the sum of all edges emanating from $a$ . However, the other condition does require the integral over the whole graph

(4)

\int_{G_{0}} \vec{k} = \int_{G_{0}} \overset{\leftarrow}{k} = χ (G) .

That is, of course, unless I’ve made another careless mistake, which we can never rule out. Urs help! :)

Posted by: Eric on October 21, 2006 7:08 AM | Permalink | Reply to this

Re: Discrete Calculus

$MathML-enabled post (click for more details).$

unless I’ve made another careless mistake

No, looks good to me (including your last correction).

This is a good move. We need to find the dictionary which tells us what various graph quantities that we are dealing with correspond to in the continuum limit.

In particular:

- what is the continuum meaning of the 0-form

(1)

f : a \mapsto \sum_{b} (ξ_{ab} + ξ_{ba})

I have a suspicion, but only based on intuition so far and likely to be wrong: could it be related to the volume element $\sqrt{g}$ ?

Posted by: urs on October 21, 2006 2:29 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Once in one of John’s seminars at UCR, I parsed his (and Jim’s) definition of groupoid cardinality as

(1)

\sum_{a} \frac{1}{\sum_{b} card hom (a, b)},

where the sum is taken over isomorphism classes of objects (or equivalently over objects, if you believe in equality of objects). This applies directly to categories (not just groupoids), generalises easily to enriched categories or n-categories, and respects addition and multiplication.

But it differs from Tom’s definition already when applied to the poset {0 < 1}: I say it has cardinality 3/2, while he says it has Euler characteristic 1.

Now, I can think of at least two ways that Tom’s definition is superior to mine: * It generalises the notion of Euler characteristic of a poset; * It generalises the notion of Euler characteristic of a digraph.

To better understand what one wants in a notion of Euler characteristic or homotopy cardinality, I’d like people to tell me what else is wrong with my definition. (Since this is perhaps a bit too idiosyncratic —why should anybody bother?—, people might also just suggest things for me to test them on.)

Posted by: Toby Bartels on October 14, 2006 5:21 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

The Euler characteristic of a compact space happens to coincide with the index of the operator $d + d^{†}$ , when the latter is defineable.

This makes me want to ask a very vague question: could it be possible that generalized notions of Euler characteristic lead to generalized notions of this operator?

Or a related question: given the Čech groupoid of a good covering of a topological space $X$ by open sets. Does the Euler characteristic of that groupoid coincide with the ordinary Euler characteristic of $X$ ?

Posted by: urs on October 18, 2006 7:12 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If someone could somehow relate an n-category to an “n-diamond” and then somehow construct an operator $d + d^{†}$ on a n-diamond, would this analogy help? :)

Posted by: Eric on October 18, 2006 8:02 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If someone could somehow relate an n-category to an “ $n$ -diamond” and then somehow construct an operator $d + d^{†}$ on a $n$ -diamond, would this analogy help?

For others reading this, I’ll translate what Eric is suggesting here:

Consider a finite oriented graph $G$ without any parallel edges (no two edges have same source and target). Let

(1)

V_{p}

be the $ℂ$ -vector space spanned by sequences of length $p$ of “composable” edges in $G$ . $V_{0}$ is the space spanned by the vertices.

Define

(2)

d : V_{0} \to V_{1}

(3)

d v : = \sum_{v_{s} \neq v} (v_{s} \to v) - \sum_{v_{t} \neq v} (v \to v_{t}),

where $v$ is a vertex, the sums run over all vertices and $v \to w$ is the edge from $v$ to $w$ if it exists, or zero otherwise.

Now divide out the minimum of relations $R$ that ensure that $d$ is nilpotent and graded Leibniz

(4)

(V^{•}, d) = (V^{•}, d) / R .

Next, choose a scalar product $〈 \cdot ∣ \cdot 〉$ on $V^{•}$ , which vanishes unless both entries are of same degree.

Let $d^{†}$ be the adjoint of $d$ with respect to that scalar product.

Now, define the index of $d + d^{†}$ as

(5)

\lim_{t \to ∞} {str}_{V^{•}} e^{- t (d + d^{†})^{2}} .

One might expect that this is related to some notion of Euler characteristic associated to $G$ , or of the category generated by it.

Is it?

Posted by: urs on October 18, 2006 8:26 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Hi,

I don’t have any answers, just some simple observations.

For the obvious choice of inner product, the adjoint $d^{†}$ turns out to be the same (functionally at least) as the boundary map $\partial$ . Therefore, the operator you wrote down

(1)

(d + \partial)^{2} = d \partial + \partial d

is the graph laplacian, which can be written in terms of the “degree matrix” and the “adjacency matrix” via

(2)

L = D - A .

I’m sure someone did this 100+ years ago, but I’m pretty sure that for a directed graph

(3)

tr (D) = \sum_{v} \deg (v) = ∣ E ∣

where $v$ are the vertices, $\deg (v)$ is the degree of vertex $v$ and |E| is the total number of directed edges in the graph.

Also, obviously

(4)

tr (I) = ∣ V ∣

where I is the identity matrix and |V| is the number of vertices.

Finally,

(5)

tr (A) = ∣ F ∣

where $A$ is the adjacency matrix and $∣ F ∣$ is the number of “loops”.

Therefore,

(6)

tr (I - L) = tr (I - D + A) = ∣ V ∣ - ∣ E ∣ + ∣ F ∣ .

This is probably 90% bogus, but hopefully it gives you some ideas :)

It would not be at all surprising to me if this can be extending to higher n-diamonds, which might help relate it to your question (maybe).

Posted by: Eric on October 18, 2006 11:00 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Therefore,

(1) $tr (I - L) = tr (I - D + A) = ∣ V ∣ - ∣ E ∣ + ∣ F ∣$

Hm, that looks pretty. I don’t think I was aware of this before.

I’ll need to think about how it relates to the expression

(2)

str \exp (- t (d + d^{†})^{2}) = str \exp (- t Δ)

that I wrote down.

While $\exp (- Δ) = I - Δ + \dots$ , the trace you write is over a different vector space (that of vertices, which I called $V_{0}$ ), while my $str$ denoted the supertrace over all of $V^{•}$ . Accordingly, $Δ = (d + d^{†})^{2}$ reduces to the $Δ$ that you mention on $V_{0}$ .

So now I am hoping that in your expression you were secretly missing something, which gets fixed once we extend the trace to all of $V^{•}$ .

Could it be hidden in this statement:

Finally,

(3) $tr (A) = ∣ F ∣$

where $A$ is the adjacency matrix and $∣ F ∣$ is the number of “loops”.

You want to identify $∣ F ∣$ with the number of faces. But is it? Faces should be triangles of edges. These don’t appear in $tr (A)$ , unless I misunderstood something. Do they?

Hence I am currently inclined to say that your formula

(4)

{tr}_{V_{0}} (I - L)

actually misses most of the faces. But that these might appear once we extend the trace over all of $V^{•}$ (including an alternating sign).

Could that be? Please correct me if I am spouting nonsense.

Finally, again for the non-experts following this, I would like to unwrap this remark of yours:

For the obvious choice of inner product, the adjoint $d^{†}$ turns out to be the same (functionally at least) as the boundary map $\partial$ .

What Eric has in mind here is this:

the “obvious inner product” on $V^{•}$ is that in which the generating basis elements of $V^{•}$ (the vertices, edges, and $R$ -classes of composable sequence of length $p$ of edges) are orthonormal.

In that basis, we compute the action of $d^{†}$ for instance on an edge $v_{1} \to v_{2}$ as follows (for any $v \in V$ )

(5)

\begin{aligned} 〈 v ∣ d^{†} (v_{1} \to v_{2}) 〉 & = 〈 d v ∣ v_{1} \to v_{2} 〉 \\ = \sum_{v_{s} \neq v} 〈 v_{s} \to v ∣ v_{1} \to v_{2} 〉 - \sum_{v_{t} \neq v} 〈 v \to v_{t} ∣ v_{1} \to v_{2} 〉 \\ = δ_{v, v_{2}} - δ_{v, v_{1}} . \end{aligned}

This is equivalent to

(6)

d^{†} (v_{1} \to v_{2}) = v_{2} - v_{1} .

And this is indeed the action of $\partial$ on the 1-simplex $v_{1} \to v_{2}$ .

Posted by: urs on October 19, 2006 11:17 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

David wrote:

I’m not sure we should be asking Tom to summarise his own paper…

No, but nonetheless he should do it if we ask him.

I remember during a discussion of my book on the Foundations of Mathematics list, which was sparked off by someone reporting John’s review, feeling a wee bit annoyed being asked to summarise what I’d written by a person who felt he didn’t have time to read it.

Well, it can be annoying when someone asks you to summarize something you wrote, but you should always do it when asked in a public forum.

Why? Because it gives lots of people a chance to learn what you’ve done - not just the lazy bum who asked the question. It also gives you a chance to look magnanimous. That’s why I was always willing to explain my work to people when they asked me to on sci.physics.research. That’s also the principle I was trying to exploit by getting Tom to explain his work now.

But, it turns out Toby was the one who broke down and typed in a definition of the Euler characteristic of a category, so everyone can see it without leaving this blog. Thanks, Toby! That’s a crucial step, because having the definition “sitting there for all to see” is the best way to get mathematicians to start poking at it and trying to prove stuff about it. If you make them leave the room and read a paper, they may get distracted and not come back.

(Our discussion is occuring in a kind of “room” here, albeit a virtual one, and for some reason opening a PDF file counts as leaving that room. I’m not sure why, but I know it’s true, and one has to just accept it.)

Anyway: now that Toby has shown us Tom’s definition, and Urs and Eric have raised an analogy with graph Laplacians, ideas start to bubble and brew…

For example, I just realized that Tom’s weightings and coweightings are functions from vertices of a directed graph to numbers. Our graph happens to be a category, but that’s not necessary for the definition to make sense.

And, the equations Toby wrote down are reminiscent of Poisson’s equation for a graph Laplacian.

Normally a graph Laplacian is defined for undirected graphs (I think). Say we have a function that maps vertices of our graph to numbers: $a \mapsto k_{a}$ Then applying the graph Laplacian gives a new function of this sort, namely: $a \mapsto k_{a} - \sum_{b} ζ_{b}^{a} k_{b}$ where $ζ_{b}^{a}$ is the number of edges joining the vertices $a$ and $b$ .

In other words, if we call the graph Laplacian $Δ$ , we have

$(Δ k)_{a} = k_{a} - \sum_{b} ζ_{b}^{a} k_{b}$

You can stick some extra numbers in this definition if you want:

$(Δ k)_{a} = α k_{a} - β \sum_{b} ζ_{b}^{a} k_{b}$

and you often do. For example, if your graph is an infinite square grid, you should take $α = 1$ and $β = 1 / 4$ , so the Laplacian takes a function of vertices and creates a new function by subtracting 1/4 times the sum of the nearest neighbor’s values. This is good because then

$Δ k = 0$

holds when $k$ is constant.

Practical people - electrical engineers who use “finite element methods” - know all about this stuff. That’s one reason Eric got interested in this business, I guess - he was doing electrical engineering or something like that, back before he decided to make vast sums of money in LA.

Anyway, Poisson’s equation is where you fix a function $f$ and look for functions $k$ such that

$Δ k = f$

If we take $f = 1$ , this says

$α k_{a} - β \sum_{b} ζ_{b}^{a} k_{b} = 1$

If we take $α = 0$ and $β = - 1$ , we get Tom’s equation

$\sum_{b} ζ_{b}^{a} k_{b} = 1$

But, Tom goes ahead and looks at two equations,

$\sum_{b} ζ_{b}^{a} k^{b} = 1$

and

$\sum_{b} ζ_{b}^{a} k_{a} = 1$

for two different functions $k_{a}$ and $k^{b}$ , the weighting and coweighting. And, if both these equations have solutions, Tom shows

$\sum_{a} k_{a} = \sum_{b} k^{b}$

and this number is the Euler characteristic of the category whose underlying graph I’ve been discussing.

So, some funny stuff is going on - but there is some relation to graph Laplacians. And we know that Laplacians show up when we compute the Euler characteristic of a manifold using the heat equation on that manifold.

So, it’s vaguely possible that Tom is secretly generalizing the usual way of computing the Euler characteristic of a manifold, by replacing the manifold with a directed graph, and modifying everything accordingly.

Okay - now someone figure out the details.

Posted by: John Baez on October 19, 2006 3:20 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Normally a graph Laplacian is defined for undirected graphs (I think).

I believe

(1)

Δ = (d + d^{†})^{2} = (d + \partial)^{2}

is defined for directed graphs, but that results like

In other words, if we call the graph Laplacian $Δ$ , we have

(2) $(Δ k)_{a} = α k_{a} - β \sum_{b} ξ_{b}^{a} k_{b}$

follow as special cases when the directed graph is assumed to have an edge

(3)

v_{2} \to v_{1}

for every

(4)

v_{1} \to v_{2} .

Let’s do the computation:

For $v$ any vertex, I write $v$ for what John calls

(5)

k_{a} : = δ_{a, v},

i.e. the 0-form supported at $v$ .

Then for any directed graph we have

(6)

\begin{aligned} Δ v & = (d + \partial)^{2} v \\ = \partial d v \\ = \sum_{v_{s} \to v} \partial (v_{s} \to v) - \sum_{v \to v_{t}} \partial (v \to v_{t}) \\ = \sum_{v_{s} \to v} (v - v_{s}) - \sum_{v \to v_{t}} (v_{t} - v) . \end{aligned}

In general, no further simplification is possible at this point. But under special conditions there is.

So now assume the graph is such that the adjacency matrix is symmetric, i.e. that for every edge $v_{1} \to v_{2}$ the reverse edge $v_{2} \to v_{1}$ exists.

Then the above becomes

(7)

\begin{aligned} Δ v & = 2 \sum_{v_{s} \to v} (v - v_{s}) \end{aligned} .

If we moreover assume that $G$ is an infinite square grid, this becomes

(8)

\begin{aligned} \frac{1}{2} Δ v & = 4 v - (northern neigbour) - (southern neigbour) - (western neigbour) - (eastern neigbour) \end{aligned} .

coinciding, up to a global factor, with the formula that John mentioned ( $α = 1$ and $β = 1 / 4$ ).

Posted by: urs on October 19, 2006 12:11 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

The mathematical universe is so highly connected. (According to David Ruelle, this is because you can pack a lot into a high-dimensional space.) At the works retreat I just returned from, we were given a tutorial on the role of Graph Laplacians in spectral clustering. The idea is that you are given a set of data points, $x_{i}$ , and a similarity measure for each pair of points, $s_{ij}$ . You’re looking to arrange the data into clusters based on intra-cluster similarity and extra-cluster dissimilarity. To this end you form an undirected graph with vertices corresponding to each data point, and a symmetric weight $w_{ij}$ on edges equal to $s_{ij}$ if it’s positive, 0 otherwise. The degree of a vertex, $d_{i}$ , is the sum of weights of edges with one end at $v_{i}$ . The diagonal matrix of $d_{i}$ is denoted $D$ , while the $w_{ij}$ are the entries of the adjacency matrix $W$ .

There are 3 forms of graph Laplacian:

$L = D - W$ is the unnormalized Laplacian.
$L_{rw} = I - D^{- 1} W$ is the random walk normalized Laplacian.
$L_{sym} = I - D^{- 1 / 2} W D^{- 1 / 2}$ is the symmetric normalized Laplacian.

In all 3 cases, the number of 0 eigenvalues is equal to the number of components of the graph. As you will see from the tutorial, other eigenvalues give more information. Hmm, might be worth seeing if there’s any connection to what John said about Tom’s construction.

Posted by: David Corfield on October 19, 2006 12:52 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

For example, I just realized that Tom’s weightings and coweightings are functions from vertices of a directed graph to numbers.

So let’s make it very explicit what this seems to be telling us:

We are talking about a space $X$ with a function $k$ on it.

(1)

k : X \to ℝ

The claim is (apparently) that if $k$ satisfies some differential equation involving a Laplace operator on $X$ (coming with a measure $d μ$ on $X$ ), then the integral

(2)

χ (X) \propto \int_{X} k d μ

is the Euler characteristic of $X$ .

(Because that’s what the expression $\sum_{a} k_{a}$ corresponds to.)

What does this way of formulating the statement do with us?

Well, it makes me think about the generalized Gauss-Bonnet theorem.

Posted by: urs on October 19, 2006 3:27 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

The claim is (apparently) that if $k$ satisfies some differential equation involving a Laplace operator on $X$ (coming with a measure $d μ$ on $X$ ), then the integral

(1) $χ (X) \propto \int_{X} k d μ$

is the Euler characteristic of $X$ .

Right. But what really freaked me out was that the differential equation was a special case of Poisson’s equation - that’s what Tom’s condition

(2)

\sum_{a} k_{a} ζ_{b}^{a} = 1

seems to be. At least, some sort of inhomogeneous equation. I’ve never heard of a way to compute Euler characteristics by doing an integral of a solution of Poisson’s equation, or any other inhomogeneous differential equation.

But maybe I’m just being dense. Maybe it’s related to the usual heat equation stuff somehow. After all, solutions of Poisson’s equation describe the $t \to ∞$ limit of a solution of the heat equation with an source term - a heat source.

But how does the source - the inhomogeneous term - get into the act?

It would be annoying if this neat stuff Tom did were so closely related to Laplacians, heat equations and their usual relation to Euler characteristic without both of them being a special case of something.

Posted by: John Baez on October 20, 2006 8:29 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

But what really freaked me out was that the differential equation was a special case of Poisson’s equation

But is it? That interpretation only works when you modify the Laplace operator by throwing in some funny constants - in particular by deleting one of the terms it consists of #.

I am a little hesitant to call the operator

(1)

k \mapsto (a \mapsto \sum_{b} ξ_{b}^{a} k (b))

a “Laplace operator”. It does not seem to share any of the properties that one would usually expect of a Laplace operator. Does it?

So that’s why I remarked # that there is another differential equation involving $k$ which comes from Tom Leinster’s condition and which reads

(2)

Δ k = f k - 2 .

This involves the “true” Laplace operator $Δ$ .

Somebody should try to figure out if this is an equation of the form satisfied by the Pfaffian of the Levi-Civita curvature 2-form of a $2 n$ -dimensional manifold.

Because that’s what the generalized Gauss-Bonnet theorem seems to suggest #.

Posted by: urs on October 20, 2006 10:27 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Somebody should try to figure out if this is an equation of the form satisfied by the Pfaffian of the Levi-Civita curvature 2-form of a 2n-dimensional manifold.

If there weren’t enough “connections” in this dialogue already, John’s other engineer friend, Robert Kotiuga, had a nice paper

Helicity functionals and metric invariance in three dimensions
Kotiuga, P.R.
IEEE Transactions on Magnetics

Abstract
The solvability, gauge invariance, and topological aspects of dual variational principles shed light on the difficulties that arise from the use of a vector potential in three dimensions in place of a stream function in two dimensions. These aspects reveal the central role of a relative de Rham complex in place of the usual Tonti diagram. By considering the `spin complex’ associated with the de Rham complex, it is seen that the helicity functional enables the scalar potential to be used in the dual role of a Lagrange multiplier which fixes the gauge of the vector potential. The metric and constitutive law independence of the helicity term is considered. The main purpose is to show how the invariant terms of the helicity functional can be used to avoid rebuilding (reassembling) large parts of the finite-element stiffness matrix in iterative computations involving constitutive laws which change with every iteration. The results are phrased in terms of differential forms

I mention it only because my vague memory tells me that it involves a pfaffian and a discrete connection. However, the pfaffian only appears when the cells are simplicial (I think).

Posted by: Eric on October 20, 2006 3:28 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

it makes me think about the generalized Gauss-Bonnet theorem.

This is very exciting. Weight is like curvature! (Coweight is like cocurvature?)

To keep our feet on the ground, maybe I should emphasize that in general, a finite category with Euler characteristic (i.e. admitting at least one weighting and at least one coweighting) admits many weightings and many coweightings. So one shouldn’t speak of “the weight” of an object, unless one has a particular weighting in mind.

But maybe that fits the curvature picture. You can deform a Riemannian manifold so that its curvature changes locally, but the “total curvature” is the Euler characteristic, which doesn’t change.

Posted by: Tom Leinster on October 20, 2006 6:23 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Weight is like curvature!

Yes. That’s what it looks like. And curvature, on a graph, is much like defect angle (over volume).

And it is known (for instance page 2 of hep-th/0605022) that the sum of defect angles over vertices is indeed the Euler characteristic! (For triangulations of 2D surfaces, that is.)

So I’d say: a weighting is a generalization of the concept of defect angle (over volume).

And that makes intuitive sense: your formula says that the weighting is the smaller, the more edges meet in a given vertex. Intuituitively: the more edges, the smaller the remaining defect angle.

Posted by: urs on October 21, 2006 3:14 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I didn’t have a chance to look at this paper the first time around. I still don’t really have time, but just want to point out that the way they define D is essentially as the “square root” of the graph Laplacian:

$D = d + \partial$

and

$D^{2} = d \partial + \partial d = Graph Laplacian = Degree Matrix - Adjacency Matrix .$

Note that the graph Laplacian is topological and does not properly incorporate the metric information contained in the Laplace-Beltrami operator. It is like choosing a non-physical metric.

Posted by: Eric on February 5, 2007 3:55 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Normally a graph Laplacian is defined for undirected graphs (I think). Say we have a function that maps vertices of our graph to numbers: $a \mapsto k_{a}$ Then applying the graph Laplacian gives a new function of this sort, namely:

(1) $a \mapsto k_{a} - \sum_{b} ξ_{b}^{a} k_{b}$

Is this formula correct in detail?

The general formula that I find # from $(d + \partial)^{2}$ is

(2)

(Δ k) (a) = \sum_{b} (ξ_{ab} + ξ_{ba}) (k (a) - k (b)) .

As a consistency check, notice for instance that this way

(3)

\sum_{a} (Δ k) (a) = 0,

as it should be.

This also seems to be consistent with writing $Δ = D - A$ , as Eric did #.

Now restrict attention to the case that $ξ_{ab} = ξ_{ba}$ .

Then Tom Leinster’s condition # implies here that

(4)

(Δ k) (a) = f (a) k (a) - 2,

where

(5)

f (a) : = \sum_{b} (ξ_{ab} + ξ_{ba}) .

So $k$ satisfies the differential equation

(6)

Δ k = f k - 2 .

Posted by: urs on October 19, 2006 4:46 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If $ξ_{ab}$ is symmetric, it looks like what you arrive at is twice what I called the unnormalized graph Laplacian, $D - W$ .

Posted by: David Corfield on October 19, 2006 7:47 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If $ξ_{ab}$ ab is symmetric, it looks like what you arrive at is twice what I called the unnormalized graph Laplacian, $D - W$ .

Yes. I think so too. As I said above, this is what Eric calls $D - A$ (“A” for “adjacency”, I guess).

Posted by: urs on October 19, 2006 8:01 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

Is this formula correct in detail?

No - I knew it wasn’t, which is why I threw in some extra fudge factors $α$ and $β$ later in that comment.

I’m working in a very rough way here, since I’m confused about something incredibly basic: namely, how you might compute the Euler characteristic as the integral of some solution of an inhomogeneous linear partial differential equation. It seems Tom is doing a discrete analogue of that - but I don’t know anything like that in the continuum case!

So, when I’ve been writing “Laplacian”, you should probably read it as “some linear differential operator”. And, when I write “Poisson’s equation”, you should read “some inhomogenous linear PDE”. Sorry!

I hope we get this figured out…

Posted by: John Baez on October 20, 2006 7:56 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

John wrote (apropos of me being asked to summarize my own paper):

The n-Category Café

Skip to the Main Content

October 11, 2006