This Week's Finds in ACT - April 25th

I wrote a long post on one of the papers I read this week: Example of my reading process: Cellular sheaves of lattices and the Tarski laplacian. See that post for the details!

Some other stuff:

Jade Master: The Open Algebraic Path Problem

This paper came out in 2020, so it’s practically ancient history. But it’s really cool! It’s about

• The problem of finding a path between two vertices on a graph
• An algebraic generalization of this where you replace “graph” by more exotic things (the “algebraic path problem”)
• An open generalization of this where you build your (generalized) graph by gluing together smaller examples.

The basic algebraic structure is a quantale - an ordered set equipped with a binary operation (compatible with the order), which has all joins. Some basic examples:

• \(\{0 \leq 1\}\) with the operation \(\vee\) (OR). Here the algebraic path problem detects the existence of a path from one vertex to another.
• \([0,\infty]\) equipped with \(+\) and given the reverse order (so join = infimum). In this case the algebraic path problem finds the length of the shortest path (\(\infty\) if there is no path).

The first observation is that this boils down to computing the pointwise join \(\bigvee_i M^i\) of all the powers of the adjacency matrix corresponding to a graph - where we simply define a “graph over a quantale” to be such an adjacency matrix. If the quantale is \(\{0,1\}\), this is a graph in the usual sense, each edge is either there or not. If the quantale is \([0,\infty]\), each edge has a certain length (which may be infinite to denote “no edge”). Thus we have “the algebraic path problem”.

The second observation is that you can “glue graphs together” by taking pushouts in a certain category of matrices, and this respects the computation of the paths above. There is a lot of very nice category theory in this.

Tom Leinster: The Magnitude Of Metric Spaces

This is an even older paper, which spawned a lively field of research (see eg here and here). This is about associating an invariant called magnitude to metric spaces, which measures their “size” in a kind of hard-to-understand way:

• The magnitude of a finite set of points, all at distance \(\infty\), is the number of points
• As the distances go to zero, the magnitude converges to one (in the above case of finitely many points)
• The magnitude of the interval \([0,t]\) is \(1 + t/2\).

I don’t think I really understand this stuff deeply, but it’s very interesting!