Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: Laplacian of an open graph

Peva Blanchard (Nov 12 2025 at 06:13):

Hi, for some project (unrelated to CT), I am studying real matrices $L$ which satisfy

$$\begin{align*} L_{aa} &\ge 0 \\ L_{ab} &\le 0 \\ L_{aa} &\ge \sum_{b \ne a} |L_{ab}| \end{align*}$$

They look like laplacian matrices, the difference being that the third condition is an inequality instead of an equality. So I'm calling them super-laplacian matrices.

A laplacian matrix $L$ is the matrix representation of the laplacian operator associated with a weighted graph. The vertices of the graph index the rows (and columns) of $L$, and there is an edge between two distinct vertices $a,b$ whenever $L_{ab} < 0$, the weight of this edge being $|L_{ab}|$. The quantity $L_{aa}$ is equal to the sum of weights of all edges incident to $a$.

I think we can also interpret a super-laplacian matrix as a laplacian operator associated with some "open graph". Roughly speaking, such an open graph is a graph where some vertices are marked as "exterior" (the remaining vertices being "interior"). The interior vertices index the rows (and columns) of $L$. The difference $L_{aa} - \sum_{b\ne a} |L_{ab}|$, where $b$ runs over interior vertices, accounts for the sum of weights of "boundary edges" connecting $a$ to exterior vertices.

I came up with a more formal definition, but, given the ACT literature about open systems, I wonder if this has been studied already.

John Baez (Nov 12 2025 at 11:31):

I don't understand one key sentence in your description. I'd hope that we have

$L_{aa} = \sum_{b\ne a} |L_{ab}|$

for all interior vertices $a$.

Anyway, I haven't seen this idea. It - or something similar, I haven't thought about it enough yet - looks very interesting. The spectral analysis of open graph Laplacians should be very cool if done right.

John Baez (Nov 12 2025 at 12:05):

The fact that I haven't seen it doesn't mean very much, though! If it appeared in the structured cospan literature I should have seen it, but if it appeared in the graph theory literature I would never have seen it.

James Deikun (Nov 12 2025 at 13:05):

I think by "interior vertices" was meant all the vertices corresponding to rows and columns of the matrix and "exterior vertices" was meant to refer to the notional vertices connected to the "unattached" edges.

I think a "super-laplacian" matrix is indeed a matrix that's an on-diagonal block of a laplacian matrix, and you can always realize it this way by adding one row and column. You add $L_{a{*}} = - \sum_{b \ne {*}} |L_{ab}|$ and $L_{{*}b} = 0$.

Peva Blanchard (Nov 12 2025 at 17:42):

James Deikun said:

I think by "interior vertices" was meant all the vertices corresponding to rows and columns of the matrix and "exterior vertices" was meant to refer to the notional vertices connected to the "unattached" edges.

I think a "super-laplacian" matrix is indeed a matrix that's an on-diagonal block of a laplacian matrix, and you can always realize it this way by adding one row and column. You add $L_{a{*}} = - \sum_{b \ne {*}} |L_{ab}|$ and $L_{{*}b} = 0$.

Yes that's right.

Here is an example
image.png

The usual laplacian of the whole graph is the matrix

$$\Delta = \begin{array}{c|ccc|cc} & a & b & c & x & y \\ \hline a & 3 & -1 & -1 & -1 & 0 \\ b & -1 & 3 & -1 & 0 & -1 \\ c & -1 & -1 & 2 & 0 & 0 \\ \hline x & -1 & 0 & 0 & 1 & 0 \\ y & 0 & -1 & 0 & 0 & 1 \end{array}$$

And if I "discard" the exterior vertices $x$ and $y$, I obtain the submatrix

$$L = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \end{pmatrix}$$

which is "super-laplacian".

Peva Blanchard (Nov 12 2025 at 17:43):

John Baez said:

Anyway, I haven't seen this idea. It - or something similar, I haven't thought about it enough yet - looks very interesting. The spectral analysis of open graph Laplacians should be very cool if done right.

Oh thanks. Well, if this is new, I might give it a try. I have some preliminary results about a (baby) co/homology. But my current formal definition of open graphs feel clumsy. I'll have a look at structured (or decorated?) cospans.

John Baez (Nov 12 2025 at 18:01):

Open graphs are one of the basic examples in structured cospan theory, so they appear in all introductions to structured cospans.

Peva Blanchard (Nov 13 2025 at 08:58):

I explained a bit more the motivation behind my question in this topic

JR (Nov 13 2025 at 19:07):

If this works it ought to (IMO) inform surgery on Riemannian manifolds. And vice versa. Like say (this is probably not the ideal reference) https://doi.org/10.1215/S0012-7094-06-13323-9

Peva Blanchard (Nov 14 2025 at 13:10):

If anyone doesn't mind, I'll do like David Egolf, and use this thread to think out loud.

Base category $\mathbb{G}$

So, I reread the definition of a structured cospan. And before even using them, I need to figure out which category $\mathbb{G}$ of graphs I want to use. I will need this category to be closed under finite colimit, and I'll probably need a left adjoint $L : \text{FinSet} \to \mathbb{G}$.

I'll start with informally stated requirements for the kind of graphs I need, and then I'll choose the most appropriate category $\mathbb{G}$. My problem is about heat propagation. Equivalently, I'm picturing random walks on graphs.

• A graph has a set of vertices, that model the available positions for the walker.
• The walker can hop from a vertex to another. There can be an edge $e$ from some vertex $x$ to another vertex $y$.
• The walker can traverse an edge forward, but also backward. For any edge $e$ from $x$ to $y$, there is a reversed edge $-e$ from $y$ to $x$.
• Each edge $e$ has a "thermal conductivity", i.e. a positive weight $\omega(e) > 0$.
• A priori, there may be multiple edges from $x$ to $y$. Maybe we will want, eventually, to merge these edges into one, and adding all their weights.

So, in my situation, I think a graph is a diagram of sets
image.png
where $s,t$ denote the source and target map, $i$ is the involution that reverse edges, and $\omega$ is the weight function.

Peva Blanchard (Nov 14 2025 at 13:16):

The part that troubles me is the involution. It has to satisfy some conditions

• $i^2 = id$
• $s i = t$, or equivalently $s = ti$
• and perhaps $i(e) \ne e$ for all $e \in E$

This last condition is a bit weird, as it refers to elements of $E$.

Peva Blanchard (Nov 14 2025 at 13:18):

The other part that troubles me is the weight $\omega$, because it refers directly to $(0,\infty)$. I remember that attributes were handled a specific way in ACSets.

Peva Blanchard (Nov 14 2025 at 13:59):

Ok, I re-read this blog post. I could present my schema as a profunctor $S$ between the category consisting of $E,V$ and $i,s,t$, and the singleton category, with single object $(0,\infty)$. And then a graph would be an attributed c-set on this schema, i.e. some $2$-cell etc. I guess this framework is useful to obtain general results about ac-sets, e.g., closure under colimits.

Peva Blanchard (Nov 14 2025 at 14:09):

Anyway, I'll stay low-brow, and define my category $\mathbb{G}$ explicitly.

Peva Blanchard (Nov 14 2025 at 22:57):

An object $G$ of $\mathbb{G}$ is specified by

• finite sets $V$ and $E$
• source and target functions $s,t :: E \to V$
• an involution $i : E \to E$, such that $si = t$, $ti = s$, $i^2 = id$, and $i(e) \ne e$ for all $e \in E$
• a weight function $\omega : E \to (0,\infty)$

John Baez (Nov 14 2025 at 23:08):

That inequality will tend to prevent your category from having nice coequalizers.... I'd avoid that if I were you. (Equations are preserved by "quotient maps", inequalities not.)

Peva Blanchard (Nov 14 2025 at 23:12):

Oh thanks. I'll follow your advice. So an object $G$ of $\mathbb{G}$ is specified by

• finite sets $V$ and $E$
• source and target functions $s,t :: E \to V$
• an involution $i : E \to E$, such that $si = t$, $ti = s$, $i^2 = id$
• a weight function $\omega : E \to (0,\infty)$

Peva Blanchard (Nov 14 2025 at 23:13):

For morphisms, I see two options.

1. The most obvious one. A morphism from $G$ to $H$ is specified by functions $f : V(G) \to V(H)$ and $g : E(G) \to E(H)$ such that source and target functions are compatible ($sg = fs$, $tg = ft$), involutions are compatible ($ig = gi$), and weights are preserved ($\omega g = \omega$).

2. Weights are accumulated. A morphism from $G$ to $H$ is specified by functions $f , g$ as above, except for the preservation of weight. Instead,

$$\omega(g(e)) = \sum_{e' ~:~ g(e') = g(e)} \omega(e')$$

I may need to think a bit more about my use case to decide which one is the best.

Peva Blanchard (Nov 14 2025 at 23:55):

At the end, I would like to relate my graphs with laplacian matrices. From my small experience with computing graph laplacians, I noticed the following behaviour. Given a graph $G$, possibly with multiple edges with the same endpoints, it has laplacian matrix $\Delta$. The off-diagonal entries of $\Delta$ aggregate the weights. Also, I can almost go the other way around: given a laplacian matrix $\Delta$, I can build a graph (with at most one edge between any two distinct vertices) which has $\Delta$ as laplacian matrix.This situation feels like an adjunction.

So I'll stick with option 2 for my morphisms.

Peva Blanchard (Nov 15 2025 at 00:23):

Now, to use the structured cospan machinery, it suffices that I

1. check that $\mathbb{G}$ has finite colimits
2. define a left-adjoint functor $L : \text{FinSet} \to \mathbb{G}$

I believe 1 is true. For (finite) coproducts, I can do pointwise (finite) coproducts. This really amounts to putting a bunch of graphs next to each other. For coequalizers, consider two parallel morphisms $a,b$ from $G$ to $H$. I want to build a coequalizer graph $Q$. Let's define

$$\begin{align*} V(Q) &= V(H) / (a(x) = b(x)) \\ E(Q) &= E(H) / (a(e) = b(e)) \end{align*}$$

where $(a(x) = b(x))$ is a short-hand notation for the equivalence relation on $V(H)$ generated by $u \simeq v$ iff there exists $x \in V(G)$ such that $u = a(x)$ and $v = b(x)$. And similarly for $(a(e) = b(e))$. The source and target maps can be defined consistenly on $E(Q)$, the involution as well (thanks to John's advice).

The weight function is not so obvious, because of my choice of morphism

Peva Blanchard (Nov 15 2025 at 07:58):

Actually, we have no choice. An edge $\epsilon \in E(Q)$ is an equivalence class (subset of edges in $E(H)$). I define its weight as the sum of weights of its members, $\omega(\epsilon) = \sum_{e\in \epsilon} \omega(e)$. This is the only way to define it if I want the quotient map $\pi : H \to Q$ to satisfy the weight aggregation rule.

Peva Blanchard (Nov 15 2025 at 08:07):

I'll skip the details on checking that $Q$, so defined, is indeed a coequalizer.

Peva Blanchard (Nov 15 2025 at 08:10):

Alright, now, the functor $L : \text{FinSet} \to \mathbb{G}$. It maps a finite set $V$ to the the graph with $V$ as set of vertices, and empty set of edges. The right adjoint is the functor that maps a graph $G$ to its set of vertices. Again, I'll skip checking the details (that they are functors, and adjoint to each other).

Peva Blanchard (Nov 15 2025 at 08:16):

Open graphs

Finally, I obtain a symmetric monoidal double category $\text{Open}(\mathbb{G})$ of open graphs.

• its objects are finite sets
• its vertical $1$-morphisms are functions between finite sets
• its horizontal $1$-morphisms are cospans $L(I) \to G \leftarrow L(J)$
• its 2-cells $(I, G, J) \to (K,H,L)$ are triples $(f,\alpha,g)$ with $f : I \to K$, $\alpha : G \to H$, and $g : J \to L$ such that the relevant squares commute.

Peva Blanchard (Nov 15 2025 at 08:25):

Associated vector spaces

Ok, now the fun part, defining the laplacian. In algebraic graph theory, we can define the laplacian by considering the vector space $C^0 = [V,\mathbb{R}]$ of functions on vertices, $C^1 = [E, \mathbb{R}]$ of functions on edges, equipping them with the obvious inner products, defining the discrete differential $\delta : C^0 \to C^1$ by

$$\delta(f) : e \mapsto f(s(e)) - f(t(e))$$

and the laplacian $\Delta : C^0 \to C^0$ as

$$\Delta = \delta^* \delta$$

where $\delta^*$ is the adjoint of $\delta$.

Peva Blanchard (Nov 15 2025 at 08:36):

Thanks to the categorical perspective, I want to try the following strategy:

• A graph $G$ is assigned a cochain complex $0 \to C^0(G) \xrightarrow{\delta} C^1(G) \to 0$.
• I want to consider a category $\mathbb{C}^{\le 1}$ of cochain complexes (of length at most $1$), with finite dimensional inner product spaces
• Check that it has finite colimits, and I can define a left adjoint $\text{FinSet} \to \mathbb{C}^{\le 1}$
• Build the sym mon double category $\text{Open}(\mathbb{C}^{\le 1})$ of open cochain complexes
• Have a monoidal double functor $\text{Open}(\mathbb{G}) \to \text{Open}(\mathbb{C}^{\le 1})$

Peva Blanchard (Nov 15 2025 at 09:52):

Not sure, if this is the right approach. Even if I have an open cochain complex, how do I obtain a "laplacian"?

John Baez (Nov 15 2025 at 10:35):

We usually get a graph Laplacian by making $C^0$ (resp. $C^1$) into inner product spaces such that vertices (resp. edges) form an orthonormal basis. This lets you define an operator $d: C^1(G) \to C^0(G)$ by

$\langle d a, b \rangle = \langle a, \delta b \rangle$

(i.e. $d$ is the adjoint operator of $\delta$). Then we get a Laplacian on $C^0(G)$ by $\Delta = d \delta$ and one on $C^1(G)$ by taking $\delta d$.

John Baez (Nov 15 2025 at 10:38):

By the way, the people I know write $d$ for your $\delta$ and $\partial$ for what I just called $d$.

Peva Blanchard (Nov 15 2025 at 12:45):

Yes. This gives me another idea. So we want define inner product spaces $C^0(G)$ and $C^1(G)$, and a linear map $d : C^0(G) \to C^1(G)$ when $G$ is an open graph, i.e. a horizontal 1-morphism in $\text{Open}(\mathbb{G})$.

So, maybe, we want to define symmetric monoidal double functors $C^0, C^1 : \text{Open}(\mathbb{G}) \to \mathbb{U}$ into a well-chosen sym mon double category $\mathbb{U}$, and a transformation $d: C^0 \Rightarrow C^1$ that satisfy some good properties.

Peva Blanchard (Nov 15 2025 at 13:03):

Defining $\mathbb{U} = \text{Open}(\mathbb{V})$

I will try to define $\mathbb{U}$ using the structured cospan construction, $\mathbb{U} = \text{Open}(\mathbb{V})$.

Let's try with $\mathbb{V}$ the category specified by:

• objects: finite dimensional inner product spaces
• morphisms: linear maps

I claim $\mathbb{V}$ is closed under finite colimits. Indeed, Orthogonal direct sums provide coproducts. Cokernel of $f : A \to B$ is provided by the projection on the orthogonal complement of the image of $f$ in $B$.

Peva Blanchard (Nov 15 2025 at 13:29):

Now, I want to define a functor $L : \text{FinSet} \to \mathbb{V}$ that preserve finite colimits.

Given a finite set $X$, I define $L(X)$ to be the free vector space equipped with the unique inner product that makes $X$ an orthonormal basis.

I don't think $L$ is a left adjoint, because, intuitively, the right adjoint would need to pick an orthonormal basis. So I'll check directly if $L$ preserve finite colimits.

Peva Blanchard (Nov 15 2025 at 13:30):

It seems clear to me that $L$ preserve finite coproducts, so I'll focus on coequalizers.
Consider two parallel functions $f,g : X \to Y$ between finite sets, and $q : Y \to Q$ their coequalizer.
image.png

We have to check that the linear map $Lq : L(Y) \to L(Q)$ is a cokernel of $h = L(f) - L(g)$.

Peva Blanchard (Nov 15 2025 at 15:09):

Peva Blanchard (Nov 15 2025 at 15:11):

We conclude that $L$ preserves finite colimits.

Wrapping everything up, the structured cospan construction gives a sym monoidal double
category $\mathbb{U} = \text{Open}(\mathbb{V})$. Concretely,

• objects: finite sets
• vertical 1-morphisms: functions between finite sets
• horizontal 1-morphisms: cospan $L(X) \to V \leftarrow L(Y)$ of finite dimensional inner product vector spaces
• 2-cells from $(X,V,Y)$ to $(X',V',Y')$: triple $(f, \alpha, g)$ with functions $f : X \to X'$, $g : Y \to Y'$, and linear map $\alpha : V \to V'$ such that the obvious squares commute.

Peva Blanchard (Nov 15 2025 at 15:45):

Functor $C^0$

I want to define a (sym mon double) functor $C^0 : \text{Open}(\mathbb{G}) \to \text{Open}(\mathbb{V})$.
Both double categories have the same vertical category $\text{FinSet}$, so the object and vertical parts of $C^0$ are clear.

Focus on the horizontal part. Consider an open graph $(X,G,Y)$, i.e. a cospan in $\mathbb{G}$

$$L(X) \to G \leftarrow L(Y)$$

The core idea is to send a graph $H \in \mathbb{G}$ to the vector space of real functions on the vertices of $H$, equipped with the obvious inner product $\langle f, g \rangle = \sum_v f(v) g(v)$. If $\phi : H \to K$ is morphism in $\mathbb{G}$, the linear map $\psi = C^0 \phi : C^0 K \to C^0 H$ is defined, for all $f \in C^0 K$

$$\psi(f) : (v \in V(H)) \to f( \phi(v) )$$

The functor so defined is contravariant.

Peva Blanchard (Nov 15 2025 at 15:45):

Thus, from the cospan in $\mathbb{G}$, we obtain a cospan in $\mathbb{V}^{op}$

$$C^0(X) \to C^0(G) \leftarrow C^0(Y)$$

Connecting with my original intent, I would like to consider this cospan as "the vector space of 0-cochains on the open graph". (But, of course, it is not an actual vector space)

Peva Blanchard (Nov 15 2025 at 15:47):

What would an element of this "space" look like? Concretely, it is a function $f$ on the vertices of the graph $G$, together with its restrictions $f|_X$ and $f|_Y$.

Peva Blanchard (Nov 15 2025 at 16:20):

This whole thing is going a bit out of control, but let's continue with 2-cells.
Consider the 2-cell in $\text{Open}(\mathbb{G})$
image.png

where $\alpha : G \to H$ is a morphism in $\mathbb{G}$, $f : X \to I$ and $g : Y \to J$ are functions.

We define a 2-cell (diagram in $\mathbb{V}^{op}$)
image.png

In this diagram $C^0(\alpha)$ represents the linear map that sends any functions $\lambda$ on the vertices of $H$ to the function $\lambda\alpha$ on the vertices of $G$. And similarly for $C^0(f), C^0(g)$.

I won't write the details, but it seems that all the squares commute indeed. Basically, it's all about copying function values or restricting to subsets of vertices.

Peva Blanchard (Nov 15 2025 at 16:35):

Now, I am realizing that $C^0$ arrives in $\text{Open}(\mathbb{V}^{op})$. But I have not verified if $\mathbb{V}^{op}$ is eligible for the structured cospan construction.

Peva Blanchard (Nov 15 2025 at 16:40):

Peva Blanchard (Nov 15 2025 at 16:48):

There are lots of other laws (vertical/horizontal compositions, ...) to check in order to state that $C^0 : \text{Open}(\mathbb{G}) \to \text{Open}(\mathbb{V}^{op})$ is a sym monoidal double functor.

I'll take a break on the details of $C^0$ here, possibly coming back to it when I am more confident that the end is worth it.

Peva Blanchard (Nov 16 2025 at 20:37):

Ok, I think I went too fast into double category territory and got lost. I'll take a step back.

John Baez (Nov 16 2025 at 22:13):

You can really delete comments by mousing to the right of them, clicking on the three dots that appear, and then clicking on "Delete message". Then we won't see these messages saying deleted.

Peva Blanchard (Nov 16 2025 at 22:18):

I tried, but a Zulip option prevents me from deleting my own messages if they are more than 1 day old.

John Baez (Nov 16 2025 at 22:19):

Oh, I guess you're right.

Peva Blanchard (Nov 17 2025 at 17:21):

Alright, I may have a more appropriate approach. Here is the general outline.

I have my category $\mathbb{G}$ of graphs (weighted multigraph, with edge involution, and morphisms that aggregate weights), and the associated double category $\text{Open}(\mathbb{G})$ of open graphs.

Let $\mathbb{V}$ be the category of finite dimensional inner product spaces with linear maps. I'll consider the double category $\text{Cospan}(\mathbb{V})$ of cospans in $\mathbb{V}$.

Next, I want to define double functors

$$\begin{align*} C^0 : \text{Open}(\mathbb{G}) &\to \text{Cospan}(\mathbb{V}) \\ C^1 : \text{Open}(\mathbb{G}) &\to \text{Cospan}(\mathbb{V}) \end{align*}$$

Then, I want to define (double) natural transformations

$$\begin{align*} d : C^0 \Rightarrow C^1 \\ d^*: C^1 \Rightarrow C^0 \end{align*}$$

Finally, I'll obtain my "open graph laplacian" as the composition

$$\Delta = d^*d : C^0 \Rightarrow C^0$$

Similarly, I'll obtain the "edge laplacian", as $dd^* : C^1 \Rightarrow C^1$.

Peva Blanchard (Nov 17 2025 at 17:45):

Functor $C^0$

definition

Vertical part

On objects, $C^0$ maps a finite set $X$ to the vector space $$C^0X$ of functions on $X$ equipped with the standard inner product.

For the vertical part, given a function $f : X \to Y$, $C^0f$ is the linear map that sends any $\phi \in C^0X$ to

$$(C^0f) \cdot \phi : y \mapsto \sum_{f(x) = y} \phi(x)$$

Horizontal part

For the horizontal part, given a cospan $L_{\mathbb{G}}X \to G \leftarrow L_{\mathbb{G}}Y$ in $\mathbb{G}$, the corresponding horizontal morphism in $\text{Cospan}(\mathbb{V})$ is

$$C^0X \to C^0G \leftarrow C^0Y$$

where
- $C^0G$ is the vector space of functions on the vertices of $G$ equipped with the standard inner product
- the map $C^0X \to C^0G$ maps a function $f : X \to \mathbb{R}$ to the function $g$ on the vertices of $G$ that restricts to $f$ on $X$ and that is zero everywhere else.
- similarly for the map $C^0Y \to C^0G$

Square part

Given a square in $\text{Open}(\mathbb{G})$
image.png

where $\alpha$ is a graph morphism.

We define a square in $\text{Cospan}(\mathbb{V})$
image.png

where $C^0\alpha$ is the linear map that takes a function $u$ on the vertices of $G$ to the function on $H$

$$(C^0\alpha)u : (y \in V(H)) \mapsto \sum_{\alpha(x) = y} u(x)$$

Peva Blanchard (Nov 17 2025 at 17:57):

Functor $C^1$

This one was trickier than I thought.

definition

Vertical part

On objects, $C^1$ sends a finite set $X$ to the zero vector space $0$.
Any function $f : X \to Y$ is sent to the zero map $0 : 0 \to 0$.

Horizontal part

Given a cospan $L_{\mathbb{G}}X \to G \leftarrow L_{\mathbb{G}}Y$, the corresponding horizontal morphism in $\text{Cospan}(\mathbb{V})$ is

$$0 \to C^1G \leftarrow 0$$

where $C^1G$ is the vector space of functions $c : E(G) \to \mathbb{R}$ on the edges of $G$ such that

$$\begin{align*} c( i (e) ) &= - c(e) \text{ (involution)} \\ s(e) = t(e) &\Rightarrow c(e) = 0 \end{align*}$$

Square part

Given a square in $\text{Open}(\mathbb{G})$
image.png

we obtain a square in $\text{Cospan}(\mathbb{V})$
image.png

where $C^1\alpha$ is the linear map that takes a function $c \in C^1G$ to the function

$$(C^1\alpha) c : (\epsilon \in E(H)) \mapsto \begin{cases} \sum_{\alpha(e) = \epsilon} c(e) &\text{if } s(\epsilon) \ne t(\epsilon) \\ 0 &\text{if } s(\epsilon) = t(\epsilon) \end{cases}$$

Peva Blanchard (Nov 17 2025 at 18:10):

Transformation $d : C^0 \Rightarrow C^1$

definition

I couldn't find the definition of a natural transformation between double functors.

But, in my case, I think it amounts (at least) to defining a family of linear maps $d_{\mathfrak{h}} : C^0G \to C^1G$ for every horizontal morphism $\mathfrak{h}$ = $L_{\mathbb{G}}X \to G \leftarrow L_{\mathbb{G}}Y$, such that the following diagram commutes

image.png

The operator $d_{\mathfrak{h}}$ is defined so as to "kill" the exterior vertices.

Formally, for any $f \in C^0G$, we define $df \in C^1G$ (omitting the subscript $\mathfrak{h}$), for all edge $e \in E(G)$, by

$$df \cdot e = \begin{cases} f(a) - f(b) &\text{if } a,b \in V(G) - Z \\ f(a) &\text{if } a \in V(G) - Z, b \in Z \\ -f(b) &\text{if } a \in Z, b \in V(G) - Z \\ 0 &\text{if } a,b \in Z \end{cases}$$

where $Z = X \cup Y$, and $s(e) = a$ and $t(e) = b$.

Peva Blanchard (Nov 17 2025 at 18:14):

Transformation $d^* : C^1 \Rightarrow C^0$

definition

The operator $d^*_{\mathfrak{h}}$ is easier to define. For any $c \in C^1G$, for all $$v \in

$$d^*c \cdot v = \sum_{s(e) = v} c(e)$$

Then, (if I'm not mistaken) the following diagram commutes
image.png

John Baez (Nov 17 2025 at 19:17):

Let $\mathbb{V}$ be the category of finite dimensional inner product spaces with linear maps.

These are arbitrary linear maps I guess, not preserving the inner product?

John Baez (Nov 17 2025 at 19:35):

this work of yours looks very interesting, though I have not gone through it all yet.

By the way, the edge involution may not be very important to all of this. I brought it into my paper Topological crystals, along with the annoying inequality $i(e) \ne e$, because it's a reasonably convenient way to make each edge "bidirectional": you can reverse an edge from a vertex $$v$ to a vertex $w$ and get one going from $w$ to $v$, and this new reversed edge is never the same as the original edge. The italicized clause only matters from edges from a vertex to itself. Without this clause you could have some edges from $v$ to $v$ that are their own reverses, and others that are not, and this can be confusing. But do these edges from a vertex to itself affect the graph Laplacian at all?

Peva Blanchard (Nov 17 2025 at 19:56):

John Baez said:

These are arbitrary linear maps I guess, not preserving the inner product?

Indeed, I'm not enforcing the linear maps to preserve the inner product. Actually, I'm not really using the inner product structures explicitly. For $d^*$, I'm giving an explicit formulation, which I derived from the usual adjoint of a linear map.

Peva Blanchard (Nov 17 2025 at 19:57):

John Baez said:

this work of yours looks very interesting, though I have not gone through it all yet.

Thank you :) I havn't gone through it all either, as there are double categorical concepts I have to experiment with.

Peva Blanchard (Nov 17 2025 at 20:03):

John Baez said:

But do these edges from a vertex to itself affect the graph Laplacian at all?

Mmh, actually these self-loops caused me some issue in defining $C^1$. I had to explicitly "kill" these self-loops. The space $C^1G$ is that of functions $c$ on the edges of $G$ that are anti-symmetric with respect to the involution, and which assigns $0$ to self-loops.

Moreover, in the usual graph-theoretic laplacian, self-loops are also killed, because the differential $df$ on this edge is automatically zero.

Peva Blanchard (Nov 17 2025 at 20:05):

I assumed bidirectional edges because of the original situation where I encountered these "super-laplacian matrices". Maybe they are not needed after all to define the open graph laplacian.

In graph theory, it is possible to define the laplacian matrix of a directed (multi)graph. This laplacian is not symmetric anymore, so the usual spectral analysis is not as convenient.

Peva Blanchard (Nov 17 2025 at 21:03):

Transformation $\Delta = d^*d$

Now, I want to have a look at what $\Delta$ does. Composing all things together, we obtain this diagram
image.png

Let $\phi \in C^0G$. We obtain, for any vertex $v \in V(G)$

$$\Delta \phi \cdot v = \chi(v) \cdot \left(\sum_{s(e) = v} \phi(v) - \chi(t(e)) \cdot \phi(t(e))\right)$$

where

$$\chi(v) = \begin{cases} 1 &\text{if } v \not\in X \cup Y \\ 0 &\text{if } v \in X \cup Y \end{cases}$$

For instance, for the graph $G$ that is line of 4 vertices, the two endpoints being exterior vertices, we obtain, as a matrix

$$\Delta = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 2 & -1 & 0 \\ 0 & -1 & 2 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$

which is indeed "super-laplacian".

Peva Blanchard (Nov 17 2025 at 21:11):

Bug

I made a mistake in my definitions: the transformation $\Delta$ is not natural ...

I think that's because I allow too many graph morphisms in $\mathbb{G}$.

John Baez (Nov 17 2025 at 21:57):

Peva Blanchard said:

John Baez said:

These are arbitrary linear maps I guess, not preserving the inner product?

Indeed, I'm not enforcing the linear maps to preserve the inner product. Actually, I'm not really using the inner product structures explicitly. For $d^*$, I'm giving an explicit formulation, which I derived from the usual adjoint of a linear map.

Good, then don't include the inner product in the definition of the category $\mathbb{V}$ - it's much nicer to let $\mathbb{V} = \mathsf{Vect}$ if that works, or maybe $\mathsf{FinVect}$ if you demand that your graphs are finite - which you probably need, for all your sums to converge!

Peva Blanchard (Nov 18 2025 at 17:24):

I'll do that!

Peva Blanchard (Nov 18 2025 at 17:26):

I found this paper. The authors introduce a generalized graph laplacian. They also consider graphs with boundaries, which they call $\partial$-graphs.

They even define a category of $\partial$-graphs, with a notion of "harmonic morphisms". That might be the kind of morphisms I need for my construction to be "natural".

Peva Blanchard (Nov 19 2025 at 06:46):

This is interesting.
An harmonic morphism $\alpha : G \to H$ between graphs has a degree function, $\deg_\alpha : V(G) \to \mathbb{R}$. This degree function comes up when relating the laplacians of $G$ and $H$.
Namely, writing $\alpha^* : C^0H \to C^0G$ for the pullback map,

$$\Delta_G \alpha^*\psi (u) = \deg_\alpha(u) \cdot \alpha^* \Delta_H \psi (u)$$

for all $\psi : V(H) \to \mathbb{R}$ and $u \in V(G)$.

Peva Blanchard (Nov 19 2025 at 06:48):

In short notation,

$$\Delta_G \alpha^* = \deg_\alpha{} \cdot \alpha^* \Delta_H$$

with the small caveat that $\deg_\alpha$ acts diagonally. So it "almost" commutes.

I'm guessing this is a case of a 2-dimensional categorical structure
image.png

Peva Blanchard (Nov 19 2025 at 07:00):

So, by restricting graph morphisms $\alpha$ to be harmonic, my candidate for the natural transformation $\Delta$ of the double functor $C^0$ into itself should satisfy the following kind of "naturalness"
image.png

John Baez (Nov 19 2025 at 10:52):

Interesting stuff!

Peva Blanchard said:

An harmonic morphism $\alpha : G \to H$ between graphs has a degree function, $\deg_\alpha : V(G) \to \mathbb{R}$. This degree function comes up when relating the laplacians of $G$ and $H$.
Namely, writing $\alpha^* : C^0H \to C^0G$ for the pullback map,

$$\Delta_G \alpha^*\psi (u) = \deg_\alpha(u) \cdot \alpha^* \Delta_H \psi (u)$$

for all $\psi : V(H) \to \mathbb{R}$ and $u \in V(G)$.

Is that the only definition of $\mathrm{deg}_\alpha$, or does it also have some other characterization? From the name "degree", I'd guess $\deg_\alpha(u)$ might be the number of vertices in $G$ that $\alpha$ maps to the vertex $u$ of $H$ - that's a bit like the degree of a continuous map.

John Baez (Nov 19 2025 at 11:07):

Btw, it's worth noting that for a map $\alpha \colon G \to H$ between finite graphs, we not only have a pullback $\alpha^\ast : C^0(H) \to C^0(G)$ but also a pushforward $\alpha_\ast: C^0(G) \to C^0(H)$, which is also very useful. The idea is that $\alpha_\ast(\psi)(u)$ is the sum of $\psi$ over all vertices that $\alpha$ maps to $u$.

I'm wondering if the definition of harmonic morphism might be cleaner in terms of the pushforward, like this:

$\Delta_H \alpha_* = \alpha_* \Delta_G$

I'm wondering if the "degree function" shows up because they're using the pullback instead of the pushfoward. (This is how degree functions sometimes show up, if I'm remembering correctly.)

Peva Blanchard (Nov 19 2025 at 12:16):

John Baez said:

Is that the only definition of $\mathrm{deg}_\alpha$, or does it also have some other characterization?

I wrote too hastily, but the relation with laplacian is not how the authors define the degree function.
The actual definition is embedded with the definition of a harmonic graph morphism.

A harmonic graph morphism $\alpha : G \to H$ between weighted graphs, is a usual graph morphism together with the condition that for any vertex $u$ in $G$, with $x = \alpha(u)$ its image in $H$, for any edge $\epsilon$ in $H$ that starts at $x$, the sum of weights of the edges $e$ in $G$ over $\epsilon$ that start at $u$ is proportional to the weight of $\epsilon$, and this coefficient $\lambda(u)$ of proportionality is the same for all $\epsilon$. In symbols,

$$\sum_{e \in E(G), s(e)=u, \alpha(e)=\epsilon} \omega(e) = \lambda(u) \cdot \omega(\epsilon)$$

The function $\lambda : V(G) \to \mathbb{R}$ is the degree function.

Peva Blanchard (Nov 19 2025 at 12:18):

The authors explicitly refer to analytic maps between Riemannian manifolds, as a source of inspiration for this definition; but I don't know enough about this topic.

Peva Blanchard (Nov 19 2025 at 12:20):

John Baez said:

I'm wondering if the definition of harmonic morphism might be cleaner in terms of the pushforward, like this:

$\Delta_H \alpha_* = \alpha_* \Delta_G$

I'm wondering if the "degree function" shows up because they're using the pullback instead of the pushfoward. (This is how degree functions sometimes show up, if I'm remembering correctly.)

I tried that! But, with the definition above, it does not work. I don't have an explicit counter-example, but the result is very easy to prove for pullbacks, so I guess pullbacks are the right things to consider.

John Baez (Nov 19 2025 at 12:49):

Okay. I'm glad the degree is not extra structure you have to choose, but something defined in terms of the map of graphs.

Peva Blanchard (Nov 19 2025 at 17:07):

The following characterization of harmonic morphisms is helpful.

A graph morphism $\alpha : G \to H$ is harmonic iff

• for any function $\psi$ on the vertices of $H$,
• for any vertex $x$ in $H$ and vertex $u \in \alpha^{-1}(x)$ in the fiber over $x$,
• if $\Delta_H \psi (x) = 0$ then $\Delta_G (\alpha^*\psi) (u) = 0$

Peva Blanchard (Nov 19 2025 at 17:10):

But then, we have a bad news: the category of graphs with harmonic morphisms is not closed under pushouts.

This means we cannot use the structured cospan construction :sad:

Peva Blanchard (Nov 19 2025 at 17:17):

Should I consider the presheaves over the category of graphs with harmonic morphisms? sounds daunting...

Peva Blanchard (Nov 19 2025 at 17:28):

Mmh, maybe there is a work-around. I need push-outs only for horizontal composition.
So, maybe

• consider the category $\mathbb{G}$ of graphs with the usual graph morphisms (it is finitely cocomplete)
• use the structured cospan construction to obtain a symmetric monoidal double category $\text{Open}(\mathbb{G})$
• and then restrict to a sub double category $\mathbb{H}$ whose vertical category consists of harmonic morphisms only.

Peva Blanchard (Nov 19 2025 at 17:30):

Mmh, but ... I would still need horizontal composition of 2-cells.

John Baez (Nov 19 2025 at 22:19):

You say "category of graphs with harmonic morphisms is not closed under pushouts" and you propose this example: the pushout of

$G \leftarrow K \to H$

where
$G = b \leftarrow a$
$H = a \to c$
and $K = a$.

But are the morphisms $K \to G$ and $K \to H$ harmonic?

Peva Blanchard (Nov 20 2025 at 09:08):

Oh indeed. I think they are. Since $K$ is just a point, its laplacian is the matrix $(0)$. So, the pullback of any harmonic function along any morphism out of $K$ is trivially harmonic. Actually the pullback of any function along any morphism out of $K$ is trivially harmonic.

But it feels like a convention issue.

Peva Blanchard (Nov 20 2025 at 09:37):

There might be a way out.

I want to consider cospans $X \to G \leftarrow Y$ (with $X$ and $Y$ being discrete finite graph) in the usual graph category.

But, I restrict the 2-cells to be of the form
image.png

where $f,g$ are functions, and $\alpha$ is a graph morphism such that

• it maps interior vertices $V(G) - X - Y$ to interior vertices $V(H) - I - J$
• its restriction to interior vertices is harmonic

I'll call these 2-cells: harmonic 2-cells.

Peva Blanchard (Nov 20 2025 at 10:25):

Then, I want to check if these kinds of 2-cells compose well horizontally.
image.png

I.e., assuming $(f,\alpha,g)$ and $(g,\beta,h)$ are harmonic 2-cells, is it true that the 2-cell $(f,\gamma,h)$ is also harmonic?

Peva Blanchard (Nov 20 2025 at 17:42):

It does not work. Since $\gamma|_G = \alpha$ and $\gamma|_H = \beta$, and $\gamma$ should be harmonic over $J$, $\alpha$ and $\beta$ must have well-defined degrees over $J$, and they must match.

Peva Blanchard (Nov 20 2025 at 17:53):

Ok, I see two paths:

• either I try to include this "matching data" in the definition of the vertical category
• or, ..., I just take a break on the double approach and focus only on the horizontal category.

John Baez (Nov 20 2025 at 22:57):

If it were me, I'd think hard about what's going on with this stuff, not worrying too much about the formalism involved until I understood what was going on, the stuff that the formalism should capture - and eventually it would all work out perfectly, because this particular stuff is bound to be beautiful. I know this is not very useful advice.

Peva Blanchard (Nov 21 2025 at 06:42):

I think I see what you mean. I think the phenomenon at hand is roughly the following.

A harmonic morphism $G \to H$ is about "locally relating diffusion (or random walks) on the two spaces". Or, pulling back a random walk on $H$ to a random walk on $G$.

Now, when composing open graphs (horizontally), we are gluing two spaces together along a specified subspace. But there must be a condition on the kinds of gluing I want, otherwise my harmonic morphisms won't go through.

It's like concatenating two differentiable functions $\alpha, \beta$ on $[0,1]$ and $[1,2]$: even if they match at $1$, $\alpha(1) = \beta(1)$, if their derivatives at $1$ don't match, the resulting function has a singularity at $1$.

In this figure
image

$\alpha$ and $\beta$ match "vertex-wise", but may not match "degree-wise".

John Baez (Nov 21 2025 at 09:13):

Now, when composing open graphs (horizontally), we are gluing two spaces together along a specified subspace. But there must be a condition on the kinds of gluing I want, otherwise my harmonic morphisms won't go through.

It's like concatenating two differentiable functions $\alpha, \beta$ on $[0,1]$ and $[1,2]$: even if they match at $1$, $\alpha(1) = \beta(1)$, if their derivatives at $1$ don't match, the resulting function has a singularity at $1$.

Right. This kind of issue shows up in a lot of places. In the study of PDE we don't usually demand that functions are harmonic on the boundary: instead, we impose boundary conditions. In TQFT, we don't glue smooth manifolds together along a boundary, because the result wouldn't be smooth: instead we thicken the boundary up to a 'collar' and glue the collars together.

Both issues would show up if one were trying to cook up a (double) category where the morphisms $M : S \to T$ are something like smooth manifolds $M$ with boundary $\partial M = S \cup T$ equipped with harmonic functions $f: M \to \mathbb{R}$. That sounds like something people studying the Laplace equation would like to do - but they'd instantly run into issues like you're hitting. So they'd try to use tricks to deal with these issues.

Peva Blanchard (Nov 21 2025 at 10:48):

I think I found a trick. I'll define the category $\text{FinSet}_\Delta$ of finite sets, with "harmonic functions".

Objects are finite sets. And a "harmonic function" from $X$ to $Y$ is a pair $(f, \deg_f)$ where $f : X \to Y$ is a usual function, and $\deg_f : X \to (0,\infty)$ is a function. I am interpreting $\deg_f$ as the degree function of $f$, although there is no laplacian to work with.