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: learning: questions

Topic: Examples of directed graphs with specific properties

Eric Forgy (Nov 10 2023 at 17:30):

Hi. One challenge I have always had is finding the right question to ask and then how to phrase it properly so people who might be able to help understand what I am talking about :sweat_smile:

I am (kind of) an engineer interested in topological spaces based on directed graphs. That aside, I'll start by just asking about directed graphs.

I am interested in directed graphs with two specific properties:

1. No intermediate edges, i.e. if (i,j) is a directed edge of the graph and (j,k) is a directed edge, then (i,k) cannot be a directed edge.
2. No opposite edges, i.e. if (i,j) is a directed edge, then (j,i) cannot be a directed edge.

First question: Does this structure ring any bells? I'd love to relate this to any work others have done before.

Second question: Is there some nice "arrow theoretic" way to express these constraints?

I think the two constraints together imply a smallest 2-cell

i ----->----- j
|             |
v             v
|             |
k ----->----- l

These, in turn, imply a smallest 3-cell, 4-cell, etc. I call these smallest cells "diamond cells".

I have an ancient "engineer's conjecture" that just as any smooth manifold can be triangulated, any smooth directed space can be "diamonated":

https://ncatlab.org/ericforgy/show/diamonation

Struggling to express this clearly :sweat_smile:

JR (Nov 10 2023 at 17:33):

Eric Forgy said:

2. No opposite edges, i.e. if (i,j) is a directed edge, then (j,i) cannot be a directed edge.

This is an oriented graph

JR (Nov 10 2023 at 17:39):

Have you seen https://arxiv.org/abs/2105.06955

Eric Forgy (Nov 10 2023 at 17:40):

Here is what GPT-4 had to say :robot:

When combined, these constraints produce a unique type of directed graph. This kind of graph could be relevant in fields like:

• Dependency Graphs: In software or systems engineering, where each edge represents a one-way dependency without shortcuts or reversals.
• Flow Networks: Especially in contexts where reverse flow is not allowed and paths are not reducible.
• Hierarchical Structures: Such as organizational charts or tree-like structures, but in a directed graph form where intermediate and reverse connections are prohibited.

I'm thinking of this as a special kind of causal set skeleton (not saying that clearly, I know. I am cursed :sweat_smile: ).

JR (Nov 10 2023 at 17:42):

I would guess (i.e., it needs proving that) you can take any transitive arc in a digraph and split it into two. I would guess that this is pretty easy to prove in the finite case because you get termination.

JR (Nov 10 2023 at 17:43):

This decimation procedure would be at the heart of the rectangular nature of your 2-cells, no?

Eric Forgy (Nov 10 2023 at 17:45):

I'm trying to summarize some of my old notes and up to that point, the closest structure that I found is a Moore complex.

Eric Forgy (Nov 10 2023 at 17:49):

Any such directed graph is also a directed acyclic graph (DAG), but the "No intermediate edges" constraint is more strict than a DAG.

JR (Nov 10 2023 at 17:49):

From p 396 of https://doi.org/10.1016/0012-365X(93)90176-T:

image.png

Eric Forgy (Nov 10 2023 at 17:51):

JR said:

From p 396 of https://doi.org/10.1016/0012-365X(93)90176-T:

image.png

Cool! Yes. Dimakis and Mueller-Hoissen often mention Hasse diagrams. Thank you for reminding me! :pray:

Eric Forgy (Nov 10 2023 at 17:52):

Given a poset, I suppose there are multiple possible Hasse diagrams?

JR (Nov 10 2023 at 17:54):

I dont think so. The poset corresponds to a DAG and the transitive reduction of that is unique.

JR (Nov 10 2023 at 17:54):

Maybe in the infinite case things are trickier? https://en.wikipedia.org/wiki/Transitive_reduction#In_directed_acyclic_graphs

Eric Forgy (Nov 10 2023 at 18:01):

Also from Wikipedia: https://en.m.wikipedia.org/wiki/Hasse_diagram#Diagram_design

Although Hasse diagrams are simple, as well as intuitive, tools for dealing with finite posets, it turns out to be rather difficult to draw "good" diagrams. The reason is that, in general, there are many different possible ways to draw a Hasse diagram for a given poset.

So, it seems that given a poset, it's Hasse diagram is a directed graph of the sort I am interested in. I think this should also imply that the graphs I am interested in generate posets, which seems obvious. This makes me think of forgetful functors and free functors, which sounds like progress toward explaining things arrow theoretically :blush:

Eric Forgy (Nov 10 2023 at 18:09):

"Transitive reduction" is an awesome pointer. Thank you so much :blush: :pray:

https://community.wolfram.com/groups/-/m/t/2312623

Causal Sets and Hasse Diagrams: The points of a causal set are most commonly visualised through the use of Hasse Diagrams, where each vertex is a point and the directed edges represent the immediate causal relations. Thus, taking the transitive reduction of a causal network yields the Hasse Diagram of the related causal set.

Eric Forgy (Nov 10 2023 at 18:23):

This seems to be the way to link our previous work to the broader causal set theory approach. And it is interesting that the Woldram article is about entanglement because linking the CST, our approach and entanglement is what brough me here to this Zulip originally :blush:

I started my stream before that Wolfram article was written so it is fun to see we were thinking in the same direction :blush:

Jencel Panic (Nov 11 2023 at 12:14):

By the way, you can think of poset, partial order, causal set, directed graph, Hasse diagram as all the same structure (they are isomorphic).

Jencel Panic (Nov 11 2023 at 12:16):

(actually a Hasse diagram is not a structure itself, but a way to visualize a structure)

Jencel Panic (Nov 11 2023 at 12:21):

The Wikipedia paragraph that you quote talks about the aestetic qualities of the diagrams, note that all the different diagrams that are shown represent the same graph.
image.png

Todd Trimble (Nov 11 2023 at 12:59):

Sorry again (Jencel), but a directed graph is not the same thing as a poset. There are connections between these notions, sure.

Jencel Panic (Nov 11 2023 at 13:50):

Ha, no need to say sorry, in fact it will be a nice exercise to make the correspondence precise, I will attempt to write it up when I have time....

John Baez (Nov 11 2023 at 17:47):

There is an functor from the category of directed graphs to the category of preorders, where an edge from x to y gives the relation x $\le$ y.

There are infinitely many nonisomorphic directed graphs with two vertices x and y, no edges going from y to x, and a nonempty set of edges going from x to y. Each one gives rise to the same preorder on {x,y}, namely the one with x $\le$ y but not y $\le$ x. This preorder is a partial order.

There are also directed graphs that give preorders that aren't partial orders.

John Baez (Nov 11 2023 at 17:49):

So, directed graphs are not "the same structure" as partial orders, or even preorders.

(On the other hand, 'poset' is just another name for a set with a partial order.)

Todd Trimble (Nov 11 2023 at 18:40):

In fact, "poset" stands for p.o.set (partially ordered set).

Usual parlance is that a partial order(ing) is a structure on a set, so there is some sort of pedantic distinction between a partial order and a poset, although there is in practical terms always some underlying substrate that supports a partial order anyway. Not to have this would be like the smile without the Cheshire Cat. (Although I guess one could say that naive Platonic sets are partially ordered by inclusion, without themselves forming a set.)

Usually when category theorists talk about directed graphs, they allow multiple parallel edges, so this would be something quite different from a poset.

Jencel Panic (Nov 11 2023 at 18:44):

I was a bit sloppy in my prev comment, so I will try to summarize the connections between the aforementioned structures.

Posets or partial orders (not sure if there is a difference between those two). They are defined by a set of points and a set of arrows, where arrows represents relationships that are transitive and antisymetric (such as "Bigger than").

Causal sets From reading the article, it seems that they are a kind of posets, which contain events, ordered by "is caused by" relation (which is transitive and antisymetric)

Hasse diagrams: They are a convenient way to represent posets graphically.

Directed graphs: Here things become interesting. Given a directed graph, you can generate the free category of that graph by just adding the arrows that are the result of composition (I suppose you have to also add the identity arrows, although the Wikipedia article doesn't mention that).

Directed graphs have just one arrow between any two points. And categories that have at most one arrow between two points are posets or preorders. And so, some directed graphs (or the categories that are generated from them) are posets.

Not all directed graphs are posets, but the question is which directed graphs are posets. I think that they are almost exactly the ones which Eric refers to.

No intermediate edges, i.e. if (i,j) is a directed edge of the graph and (j,k) is a directed edge, then (i,k) cannot be a directed edge.

Note that although a directed graph has just one arrow between given two points, there might be more than one arrows when we add the compositional arrows, that is, if the graph has $f: I \to J$, $g: J \to K$, and $h: I \to K$, then the category would also have $g \circ f : I \to K$ and so you would end up with two $I \to K$ morphisms. This requirement exclude all those cases.

No opposite edges, i.e. if (i,j) is a directed edge, then (j,i) cannot be a directed edge.

This requirement clearly expresses the law of anti-symmetry.

There is one requirement missing, namely that there should not be any circular sets of arrows (e.g $I \to J$, $J \to K$ $K \to I$) as these would lead to symmetric relationships, but other than that I think that the directed graphs Eric refers to can be translated to posets.

I hope this make sense. And if it doesn't, they say that the best way to get the correct answer on the Internet is to post the wrong answer :)

Jencel Panic (Nov 11 2023 at 18:48):

@John Baez @Todd Trimble I wrote all this before reading your last comments, btw.

Eric Forgy (Nov 11 2023 at 20:19):

Thanks you, everyone :pray:

Let's give the kind of directed graph I am interested in, i.e. those with no intermediate edges and no opposites, a name:

Definition: A diamond graph (not to be confused with this) is a directed graph with:

• No intermediate edges, i.e. if (i,j) is a edge from i to j, and (j,k) is an edge from j to k, then there is no edge (i,k)
• No opposite edges, i.e. if (i,j) is an edge, then (j,i) is not an edge
• No self loops, i.e. (i,i) is not an edge

I've learned that a diamond graph can be obtained as the transitive reduction of a poset. That helps link discrete differential geometry (DDG) and causal set theory (CST). However, I feel this viewpoint puts these special graphs in a kind of secondary position of importance. I think these things are fundamentally important.

Given any diamond graph, we can obtain a kind of path algebra and first-order differential calculus with unit

$$1 = \sum_i e(i)$$

and differential

$$df := [G,f]$$

where

$$G = \sum_{i,j} e(i,j)$$

and

$$f = \sum_i f(i) e(i).$$

With diamond graphs, we can construct higher order cells, i.e. $n$-diamonds, by requiring $d^2 = 0$, which is satisfied if

$$G^2 = \sum_{i,j,k} e(i,j,k) = 0.$$

This is progress. Thank you again :pray:

To summarize:

• Given a poset, we can obtain a diamond graph via transitive reduction
• Given a diamond graph, we can obtain a nocommutative graded differential algebra that represents a form of discrete (noncomutative) differential geometry.

However, we don't need to start with a poset. We could just start with a diamond graph. This will generate both the poset and the DGA.

David Egolf (Nov 14 2023 at 03:27):

I notice that the nLab has a rather large disambiguation page on "directed graph": here. It's not clear to me which particular concept described on that page @Eric Forgy is interested in!

Eric Forgy (Nov 14 2023 at 03:28):

The kind of directed graph I am interested in is not on that page (I helped create that page - I literally create the first revision back in 2008) :blush:

David Egolf (Nov 14 2023 at 03:30):

I notice that above you were using the term "directed graph". For example:
Eric Forgy said:

I am interested in directed graphs with two specific properties:

Could you maybe explain what you mean by "directed graphs" in this sentence?

To clarify, I assume there is some basic concept of "directed graph" you are starting with, and then you wish to investigate particular examples which satisfy certain additional properties. I'm curious what the basic concept is that you have in mind - before we start talking about additional properties.

Eric Forgy (Nov 14 2023 at 03:34):

Sure! What I am interested in is a special kind of directed graphs, but there are directed graphs that are not of the kind I am interested in. But here is a nice discussion of the directed graph.

David Egolf (Nov 14 2023 at 03:35):

Ah, I see! So by "directed graph" you mean what the nlab calls a "digraph". Thanks for explaining that. I was guessing you maybe meant what the nlab calls a "quiver".

Eric Forgy (Nov 14 2023 at 03:40):

I think digraphs and quivers are equivalent :sweat_smile: Both as opposed to directed multigraphs.

From quiver:

While therefore, as concepts in themselves, quiver and directed graph are just the same, using the term quiver serves to indicate certain constructions that one is interested in (a concept with an attitude), notably the corresponding quiver representations which much of the theory revolves around. The key result here is Gabriel's theorem from the same article Gabriel 72 that introduced the terminology quiver.

David Egolf (Nov 14 2023 at 03:47):

Here is one big difference between quivers and digraphs (assuming I'm reading the nLab correctly!):

• in a quiver you can have multiple arrows from one vertex to another vertex
• in a digraph, you can't have multiple arrows from one vertex to another vertex

Another big difference is this:

• in a quiver, you can have an arrow from a vertex back to that vertex
• in a digraph, you can't have an arrow from a vertex back to that vertex

I believe that every digraph can be thought of as a quiver. But there are quivers that have features that aren't allowed in digraphs!

David Egolf (Nov 14 2023 at 03:57):

So, I think I'm really asking this:
When you say "directed graph", do you mean a graph where...

• ...there could possibly be multiple arrows with the same starting and ending vertices?
• ...there could possibly be loops?

...or do you wish to disallow these features? (Or maybe you don't have a strong opinion either way!)

I suspect you don't want to allow multiple arrows with the same starting and ending vertices - as you indicate that you do not want directed multigraphs. But I'm less sure how you feel about allowing loops!

Eric Forgy (Nov 14 2023 at 05:52):

This is the definition I am interested in, which excludes self loops and with the addition that, as you rightly point out, there is just one edge between any two nodes (although there are applications where I would consider multigraphs, but not here). I discussed that a bit here.

John Baez (Nov 14 2023 at 07:24):

Okay, those are completely different from quivers.

Eric Forgy (Nov 14 2023 at 07:26):

nLab said directed graphs were the same as quivers. Not me. And I never mentioned quivers in anything I've said above (other than quote nLab).

John Baez (Nov 14 2023 at 07:27):

It does? Where? Are directed graphs supposed to be the same as digraphs?

Quivers are arguably the logically simplest concept: a quiver is two sets $E$, $V$ and two functions $s, t: E \to V$.

Eric Forgy (Nov 14 2023 at 07:28):

https://categorytheory.zulipchat.com/#narrow/stream/229199-learning.3A-questions/topic/Examples.20of.20directed.20graphs.20with.20specific.20properties/near/401899045

John Baez (Nov 14 2023 at 07:29):

Okay, thanks. "Directed graph" is probably used to mean different things, one being a quiver, but this remark needs to be fixed. David Egolf seems to be reading a different, better part of the nLab:

David Egolf said:

Here is one big difference between quivers and digraphs (assuming I'm reading the nLab correctly!):

• in a quiver you can have multiple arrows from one vertex to another vertex
• in a digraph, you can't have multiple arrows from one vertex to another vertex

Another big difference is this:

• in a quiver, you can have an arrow from a vertex back to that vertex
• in a digraph, you can't have an arrow from a vertex back to that vertex

I believe that every digraph can be thought of as a quiver. But there are quivers that have features that aren't allowed in digraphs!

John Baez (Nov 14 2023 at 07:31):

It's possible "digraph" is not being treated as a synonym for "directed graph" in some parts of the nLab. But anyway, David has listed the two (and only) ways in which digraphs are less general than quivers.

Eric Forgy (Nov 14 2023 at 07:33):

Apparently, it is not so easy to keep all this straight: https://ncatlab.org/nlab/show/digraph#idea

In combinatorics, a digraph (a shortening of directed graph) consists of a set and a binary relation on that set that is irreflexive.

Mike Shulman (Nov 14 2023 at 07:35):

It's pretty common in category theory for "directed graph", or even just "graph", to refer to a quiver.

Mike Shulman (Nov 14 2023 at 07:36):

In my experience, it doesn't usually get shortened to "digraph" in that context, but I wouldn't be surprised if it happens.

John Baez (Nov 14 2023 at 07:49):

I don't mind using "graph" to mean "quiver", since "graph" is so bloody ambiguous that you should assume you don't know what it means unless the person saying it either told you or conveys, by their general manner, what kind of person they are thus what they'd mean by "graph".

John Baez (Nov 14 2023 at 07:50):

On the other hand I'd tend to feel that anyone who uses "directed graph" to mean "quiver" is almost deliberately trying to ignore the subject called graph theory and what graph theorists mean by "directed graph".

John Baez (Nov 14 2023 at 07:52):

And if someone uses "digraph" to mean "quiver" I'd feel sure they are flaunting their disrespect for graph theorists. :upside_down:

John Baez (Nov 14 2023 at 07:53):

I've tackled that nLab article that gave Eric Forgy the unfortunate impression that

nLab said directed graphs were the same as quivers.

Mike Shulman (Nov 14 2023 at 07:53):

That doesn't seem fair to me. I don't think there's any reason for it to be obvious to someone who's not an expert in graph theory that graph theorists feel very strongly that a "directed graph" means a "directed simple graph", since it is often given a more expansive meaning.

Mike Shulman (Nov 14 2023 at 07:54):

E.g. on wikipedia I read

In one more general sense of the term allowing multiple edges, a directed graph is an ordered triple G = (V, E, ϕ) ... To avoid ambiguity, this type of object may be called precisely a directed multigraph.

Mike Shulman (Nov 14 2023 at 07:55):

I don't think someone reading that page and concluding that "directed graph" can refer to a directed multigraph can be said to be trying to ignore graph theory.

Mike Shulman (Nov 14 2023 at 07:59):

And while I'm certainly not an expert in graph theory, I've taught introductions to graph theory several times in my discrete math class, and multigraphs do come up. For instance, the famous Seven Bridges of Konigsburg graph, which inspired the subject of Eulerian paths, is an (undirected) multigraph. And its Wikipedia page just says that "The resulting mathematical structure is a graph" and doesn't even include the word "multigraph".

Eric Forgy (Nov 14 2023 at 08:01):

Here is a disambiguation page David referred to that attempts to sort this out: https://ncatlab.org/nlab/show/directed+graph

John Baez (Nov 14 2023 at 08:01):

That Wikipedia article already gave the usual definition of directed graph in boldface. Now it's trying to politely say that if this is what you think a directed graph is, you should instead call it a directed multigraph. Unfortunately it also put boldface on this definition of directed graph, which is confusing. I've removed that.

Luckily the main Wikipedia article on directed graphs gives the usual, and I'd say "correct", definition of directed graph.

As for the nLab article, it started by acting like quivers and directed graphs are "just the same":

While therefore, as concepts in themselves, quiver and directed graph are just the same, using the term quiver serves to indicate certain constructions that one is interested in (a concept with an attitude), notably the corresponding quiver representations which much of the theory revolves around.

But then it turned around and said

On the other hand, beware that in graph theory, the term “directed graph” is often taken to mean that there is at most one edge from one vertex to another.

That is: among mathematicians who actually devote their lives to studying graphs, "directed graph" is usually used to mean something else.

I have tried to improve this nLab article.

Eric Forgy (Nov 14 2023 at 08:09):

I took the approach of "quiver", i.e. just make up a new name entirely to (hopefully) avoid confusion :sweat_smile:

The graphs I want to study are "diamonds" :diamond_with_a_dot: :blush:

Mike Shulman (Nov 14 2023 at 08:10):

John Baez said:

That Wikipedia article already gave the usual definition of directed graph in boldface. Now it's trying to politely say that if this is what you think a directed graph is, you should instead call it a directed multigraph. Unfortunately it's also putting boldface on this definition of directed graph, which is confusing.

That's not how it reads to me. The two definitions given are phrased very parallely.

In one restricted but very common sense of the term,[8] a directed graph is...To avoid ambiguity, this type of object may be called precisely a directed simple graph.
...
In one more general sense of the term allowing multiple edges,[8] a directed graph is... To avoid ambiguity, this type of object may be called precisely a directed multigraph.

The "to avoid ambiguity" sentences are written precisely the same, so I don't see any reason a reader should assume that "directed multigraph" is the "correct" name for the latter one. The only indication of any difference in importance between the two definitions is the "very common" on the first one. Both even have the same citation to a graph theory book.

Mike Shulman (Nov 14 2023 at 08:12):

I'm not disagreeing that graph theorists use "directed graph" almost exclusively for the simple case. I'm just saying that, given that references like this are easy to find (Wikipedia is just one example), I don't think it's fair to say that someone who uses it for the multi case is deliberately ignoring graph theory.

John Baez (Nov 14 2023 at 08:14):

Eric Forgy said:

Apparently, it is not so easy to keep all this straight:

Indeed! It's a famous quagmire: there are at least 12 important kinds of graph: directed/nondirected, multiple edges/single edges, allowing self loops/not allowing self-loops/having distinguished self-loops. And people have the annoying habit of being unclear about these things and expecting other people to get the idea. I particularly dislike definitions of the sort "a multigraph is a graph that allows multiple edges between vertices" - except when you're in the mood for a vague hand-wave - since it's defining "multigraph" in a way that assumes you already agree on what a graph is, and are "just changing this one thing".

In combinatorics, a digraph (a shortening of directed graph) consists of a set and a binary relation on that set that is irreflexive.

That is the usual definition of digraph - or if you prefer, it's equivalent to the usual definition of digraph.

John Baez (Nov 14 2023 at 08:16):

For example, you'll notice that the Wikipedia article Directed graph starts by giving an incredibly vague rough definition of directed graph = digraph, and then gives a definition equivalent to this one.

John Baez (Nov 14 2023 at 08:18):

Mike Shulman said:

I'm not disagreeing that graph theorists use "directed graph" almost exclusively for the simple case. I'm just saying that, given that references like this are easy to find (Wikipedia is just one example), I don't think it's fair to say that someone who uses it for the multi case is deliberately ignoring graph theory.

I think you sometimes take my jocular gibes as conjectures to be refuted.

John Baez (Nov 14 2023 at 08:19):

I ended the passage you're arguing about with a smiley face, precisely to lessen the chance of this.

Mike Shulman (Nov 14 2023 at 08:22):

Sorry. :upside_down: is one of the emojis for which I never have any idea what it means, plus it wasn't clear to me that it applied to the whole sequence of comments rather than just the one to which it was appended.

Eric Forgy (Nov 14 2023 at 08:22):

Now, this is fun: https://ncatlab.org/nlab/show/n-poset

And this: https://ncatlab.org/nlab/show/Hasse+n-graph

Which leads to this: https://nforum.ncatlab.org/discussion/237/all-kdiagrams-commute/

Good times :smiley:

John Baez (Nov 14 2023 at 08:25):

Mike Shulman said:

Sorry. :upside_down: is one of the emojis for which I never have any idea what it means, plus it wasn't clear to me that it applied to the whole sequence of comments rather than just the one to which it was appended.

I'm happy to tell anyone who asks that I use :upside_down: to mean "just kidding" or "not completely serious here: don't sue me". Nobody uses it but me, basically, but that's what I always mean by it.

Mike Shulman (Nov 14 2023 at 08:33):

I feel like at some point in the past I complained about not knowing what emojis meant, and was told that I could basically ignore them because they don't convey important information. And I don't want to make a habit of asking everyone what they mean by their emojis, because people use so many emojis that if I did that it would overwhelm every conversation.

But speaking of overwhelming conversations, this is rather off the rails, so I'll stop now and wish I could go to bed instead of grading midterms. (-:

Eric Forgy (Nov 14 2023 at 08:36):

I had to go back in time to revision 40 to find the conversation that the n-Forum refers to. Here it is: https://ncatlab.org/nlab/revision/preorder/40 :blush:

John Baez (Nov 14 2023 at 08:56):

Mike Shulman said:

I feel like at some point in the past I complained about not knowing what emojis meant, and was told that I could basically ignore them because they don't convey important information.

Well, whoever said that probably ended that comment with :rolling_eyes:. It's not true. Emojis are communication like everything else, and like all forms of communication you either "just pick it up" or ask. But anyway, good luck on those midterms.

Spencer Breiner (Nov 14 2023 at 11:59):

(deleted)

John Baez (Nov 14 2023 at 12:06):

By the way, @Spencer Breiner, you can truly delete your comment by clicking on the 3 gray dots at the right of that comment and choosing "Delete comment". I used to do this for other people back when I was a moderator, but I no longer have that power.

Spencer Breiner (Nov 14 2023 at 12:08):

John Baez said:

Indeed! It's a famous quagmire: there are at least 12 important kinds of graph: directed/nondirected, multiple edges/single edges, allowing self loops/not allowing self-loops/having distinguished self-loops.

What are the rest?

Another possible distinction: when graph theorists talk about (simple) directed graphs, do they mean $|{\rm Edge}(x,y)|≤1$ or $|{\rm Edge}(x,y) + {\rm Edge}(y,x)|≤1$?

Todd Trimble (Nov 14 2023 at 12:09):

Anyway, the nLab mentions that "quiver" is one of those concepts with an attitude*, and partly for that reason I don't use it, but mainly I don't use it because "directed graph" is what I grew up saying. I don't talk with graph theorists that often, so I generally feel safe inside my bubble, but if/when I do, then I get this issue sorted out tout de suite. I myself typically add in the word "simple" if I don't want multiple parallel edges, and if I also mean "irreflexive", then I guess I should say so but maybe haven't always.

*And now I see "pseudograph" mentioned at nLab: yikes!

Todd Trimble (Nov 14 2023 at 12:09):

"Digraph" is not part of my vocabulary if I mean to speak of directed graphs in my sense (quiver). I use it in the discrete math classroom for the "simple" notion.

Spencer Breiner (Nov 14 2023 at 12:10):

Another question: does anyone know of some interesting graph theory on simple digraphs that doesn't generalize to the multi- case? Are there good reasons for rejecting multigraphs?

Todd Trimble (Nov 14 2023 at 12:10):

[Toby Bartels was involved in a lot of those nLab discussions. He (oh wait, I think it's "they" now) also counseled "categorial" where I would naturally say "categorical", I guess to avoid confusion with "categorical" in the model theorist's sense. But I was never interested in following that counsel.]

JR (Nov 14 2023 at 13:25):

Mike Shulman said:

I don't think someone reading that page and concluding that "directed graph" can refer to a directed multigraph can be said to be trying to ignore graph theory.

I have never seen a combinatorist, much less a graph theorist, use the word digraph (versus perhaps "directed graph" on rare occasions) without meaning single arcs between vertices.

Todd Trimble (Nov 14 2023 at 13:30):

John: thanks!

In response to Spencer's question: I don't have a great response in hand to the exact question, but since this is a category theory zulip, I guess no one will mind my mentioning that the category of directed graphs = quivers is a topos, whereas various types of simple graphs often form a quasitopos but not a topos. For example, if "graph" is taken to mean a set equipped with a symmetric binary relation, then those graphs form a quasitopos. Same with sets equipped with a reflexive symmetric relation.

JR (Nov 14 2023 at 13:40):

Spencer Breiner said:

Another question: does anyone know of some interesting graph theory on simple digraphs that doesn't generalize to the multi- case? Are there good reasons for rejecting multigraphs?

It's more that most questions that graph theorists ask of digraphs can be asked of quivers, but pointlessly: i.e., they factor through the forgetful functor. Typically these are questions of reachability, distance, flows, structural properties (e.g., Hamiltonicity, cycles), etc.

JR (Nov 14 2023 at 13:47):

Though I suppose spectral (or more generally some other aspects of algebraic) graph theory as realized for digraphs would fit the bill specifically.

Mike Shulman (Nov 14 2023 at 16:56):

JR said:

Mike Shulman said:

I don't think someone reading that page and concluding that "directed graph" can refer to a directed multigraph can be said to be trying to ignore graph theory.

I have never seen a combinatorist, much less a graph theorist, use the word digraph (versus perhaps "directed graph" on rare occasions) without meaning single arcs between vertices.

I didn't disagree with this. Rather, I was saying that publicly available references for the definition of "directed graph" don't always convey that information to someone who may want to align with graph-theoretic terminology but may not personally know any graph theorists.

John Baez (Nov 14 2023 at 17:14):

Eric Forgy said:

I took the approach of "quiver", i.e. just make up a new name entirely to (hopefully) avoid confusion :sweat_smile:

The graphs I want to study are "diamonds" :diamond_with_a_dot: :blush:

That's good, btw.

Eric Forgy (Nov 14 2023 at 17:52):

Spencer Breiner said:

Another question: does anyone know of some interesting graph theory on simple digraphs that doesn't generalize to the multi- case? Are there good reasons for rejecting multigraphs?

Kind of the opposite happened for me. In all my work, I always used simple directed graphs, but then when John started writing about electrical networks, you need to consider parallel elements, so I had to augment my notation to support multigraphs. The result was kind of neat: Electrical networks.

Eric Forgy (Nov 14 2023 at 18:41):

Eric Forgy said:

Kind of the opposite happened for me. In all my work, I always used simple directed graphs, but then when John started writing about electrical networks, you need to consider parallel elements, so I had to augment my notation to support multigraphs. The result was kind of neat: Electrical networks.

Can't resist saying something about this.
In discrete calculus, you get a derivation

$$df = [G,f]$$

as the commutator with the discrete 1-form

$$G = \sum_{i,j} e^{i,j}$$

representing the sum of all directed edges.

Ohm's law, using discrete calculus, can be written as

$$[G,V] = I$$

where $G$ is a conductance 1-form

$$G = \sum_{i,j} G_{i,j} e^{i,j}$$

Notational similarities aside, if you have multiple edges connecting $i$ to $j$, then I show the conductance is merely the "number" of edges, which implies a fundamental discreteness to conductance so that any conductance is a multiple of some smallest conductance.

It is just so fun to explore this stuff :blush:

Eric Forgy (Nov 14 2023 at 18:47):

If anyone is interested in seeing real-world applications of this stuff in decentralized finance, I have a more recent blog post here:

• Discrete Calculus for DeFi Math

This is the basis of my new protocol (which I promised not to shill), but the math is still fun to talk about :blush:

David Egolf (Nov 14 2023 at 19:15):

I would like to better understand the idea this thread started out with.

I now believe I understand what kind of structure is meant by the quote below, thanks to the discussion above:

Eric Forgy said:

Definition: A diamond graph (not to be confused with this) is a directed graph with:

• No intermediate edges, i.e. if (i,j) is a edge from i to j, and (j,k) is an edge from j to k, then there is no edge (i,k)
• No opposite edges, i.e. if (i,j) is an edge, then (j,i) is not an edge
• No self loops, i.e. (i,i) is not an edge

If you wouldn't mind explaining, @Eric Forgy, I'm curious what leads you to consider these particular graphs. I'm especially interested in understanding why you don't want "intermediate edges". I've been thinking recently about modelling things with categories, and one of the things I like about categories is that you can compose morphisms. This is good, I believe, for modelling applications where the following situation occurs:

• You know how to make $B$ from $A$, and $C$ from $B$...
• ...and as a result, you now know how to make $C$ from $A$

Or maybe this situation occurs:

• You know how to travel to $B$ from $A$, and to $C$ from $B$...
• ...and as a result, you now know how to travel to $C$ from $A$

In both of the scenarios I just mentioned, it's helpful to be able to compose things of interest to get a new thing of interest. So it intrigues me that you disallow 'intermediate edges': in a diamond graph, if you have a edge from i to j, and you have an edge from j to k, then you never have an edge from i to k.

This kind of structure seems very non-compositional, and I am intrigued by the context that leads to this requirement!

JR (Nov 14 2023 at 19:48):

Speculating: if you're _given_ generating morphisms on that structure then you get the rest by composition.

Eric Forgy (Nov 14 2023 at 19:55):

Hi David. It is definitely neat and useful to associate directed edges with morphisms in a category, but there is no requirement to do so. Given a diamond, which is essentially a Hasse diagram, you can generate a category and recover the intermediate edges, but that would be a different structure than the one I am studying.

I was always motivated by electromagnetic theory and the cleanest way to express Maxwell's equations utilitizes the langauge of exterior calculus and differential forms. Thinking hard about this for years and years, I came to believe that two properties of the exterior derivative $d$ are fundamental to physics, i.e.

1. $d^2 = 0$
2. $d(\alpha\beta) = (d\alpha)\beta + (-1)^{|\alpha|} \alpha (d\beta)$

In a discrete world, this brings in cool things like algebraic topology, cochains, cup products, etc. Stuff that stretched my brain (but people here eat for breakfast). I eventually stumbled on some work by Dimakis and Mueller-Hoissen (see my intro).

From that work, you can see that any directed graph gives raise to a fully robust first-order differential calculus. There is some neat math that goes into that I talked about here.

In a nutshell, defining "multiplication" as a form of path concatenation, you can obtain a differential $d$ that satsfies the two properties above, i.e. nilpotency and graded product rule, on discrete 0-forms via

$$\begin{aligned} de^i &= G e^i - e^i G \\ &= \sum_j \left(e^{j,i} - e^{i,j}\right) \end{aligned}$$

and on discrete 1-forms via

$$\begin{aligned} de^{i,j} &= G e^{i,j} -e^i G e^j + e^{i,j} G \\ &= \sum_k \left(e^{k,i,j} - e^{i,k,j} + e^{i,j,k}\right) \end{aligned}$$

where $G$ is the discrete 1-form representing the sum of all directed edges I mentioned above.

On discrete 2-forms it proceeds in the same way

$$\begin{aligned} d e^{i,j,k} = G e^{i,j,k} - e^i G e^{j,k} + e^{i,j} G e^k - e^{i,j,k} G \end{aligned}$$

with the extension to discrete $n$-forms obvious. You just stick in "intermediate edges" in an alternating sum and you end up with a cool form of discrete graded differential algebra which can be used to solve practical problems in computational physics (and finance).

If your directed graph has no intermediate edges to start with, several magical things happen. For one, all those terms in the alternating sum with intermediate edges vanish and you just get the first and last terms remaining:

1. $d e^i = G e^i - e^i G$
2. $d e^{i,j} = G e^{i,j} + e^{i,j} G$
3. $de^{i,j,k} = G e^{i,j,k} - e^{i,j,k} G$

In general, we have

$$d e^{i_1, \cdots , i_p} = G e^{i_1, \cdots, i_p} - (-1)^p e^{i_1, \cdots, i_p}$$

which is just a graded commutator so that

$$d\alpha = [G,\alpha].$$

(To be continued...)

Eric Forgy (Nov 14 2023 at 20:02):

BUT... I kind of lied (not in a malicious way). You only get a proper graded derivation $d$ from those alternating sums if your graph contains all edges, i.e. it needs to be a complete graph (which leads to the universal differential envelope :exploding_head: ).

When you start deleting edges from the complete graph, the nipotency of $d$ imposes relationships between edges. In a "diamond graph", we get

$$d^2 \alpha = [G^2, \alpha]$$

so we require

$$G^2 = 0.$$

This is pretty neat and powerful. For example, if this is your directed graph:

i ----->----- j
|             |
v             v
|             |
k ----->----- l

then the condition $G^2 = 0$ implies that

$$e^{i,j,l} = -e^{i,k,l}$$

which means that we actually have an oriented 2-cell here. I think you can see why I call these "diamonds" now :blush:

JR (Nov 14 2023 at 20:04):

OK so you can get these gizmos by having vertices of the form $(x,t)$ where $t \in \mathbb{Z}$ and disallowing "spacelike" arcs right? Is that what you do?

Eric Forgy (Nov 14 2023 at 20:05):

Check out sections 2.2 and 2.3 of our paper for more info. It is pretty fun stuff, but the notation is admittedly a bit of a buzz kill :sweat_smile:

https://arxiv.org/abs/math-ph/0407005

Eric Forgy (Nov 14 2023 at 20:08):

JR said:

OK so you can get these gizmos by having vertices of the form $(x,t)$ where $t \in \mathbb{Z}$ and disallowing "spacelike" arcs right? Is that what you do?

You get the idea :thumbs_up: I discuss this here:

• Network Theory and Discrete Calculus – The Binary Tree

The binary tree is a particularly simple (and useful!) form of diamond.

The iidea is that traversing an edge requires some finite amount of time. In fact, the time coordinate is just

$$dt = \Delta t G$$

:blush:

JR (Nov 14 2023 at 20:12):

So IIRC Dimakis and Mueller-Hoissen cohomology specifically grabs onto diamonds (and triangles) which is part of its allure right?

Eric Forgy (Nov 14 2023 at 20:21):

Well, to clarify, I know you're not suggesting they are , but triangles are not diamonds because of the intermediate edge, so our work focuses on diamonds, which is more specialized than D&MH. This specialization results in some magical mimetic properties.

For example, in the intro to our paper:

With respect to this fact it is interesting that on topologically hypercubic graphs there is a preferred inner product $\langle\cdot |\cdot\rangle$ which renders all edges lightlike and induces a pseudo-Riemannian metric on the discrete space. A notion of time hence appears naturally in this framework.

I am pretty sure that this property carries over to non-hypercubic graphs as long as it's transitive reduction is a diamond, i.e. if it is a poset (I think).

David Egolf (Nov 15 2023 at 00:57):

Thanks for your explanation above, @Eric Forgy ! I would need to do some more work to more clearly understand the ideas and notation you reference from "discrete differential calculus" (e.g. as developed here).

But, very roughly, it sounds like we have some linear operator $d$ that "moves us up dimensions". If we put in a point (like a vertex in our digraph?), it spits out some linear combination of arrows in our digraph, I think. Specifically, I think you indicate that for a vertex $e^i$, $d(e^i)$ is the sum of the arrows entering $i$ minus the sum of the arrows leaving $i$. I then guess that we can apply $d$ to an arrow in our digraph to get some kind of sum of 2D objects which are described by specifying three ordered vertices.

You end up with a formula that describes how to compute $d$ for inputs of various "dimension" (e.g. vertices, arrows, and higher dimensional things). I think you are saying that if our digraph doesn't have "intermediate edges", then the formula to compute $d$ becomes a lot simpler!

Eric Forgy (Nov 15 2023 at 02:22):

You got it! :partying_face:

The fun part comes when you start working with discrete 0-forms as linear combinations of vertices, i.e.

$$f = \sum_i f_i e^i$$

and compute

$$\begin{aligned} df &= [G,f] \\ &= Gf - fG \\ &= \sum_{i,j} (f_j - f_i) e^{i,j}. \end{aligned}$$

This is the discrete version of the gradient from vector calculus.

Then for a discrete 1-form

$$\begin{aligned} d\alpha &= [G,\alpha] \\ &= G\alpha + \alpha G \\ &= \sum_{i,j,k} (\alpha_{i,j} + \alpha_{j,k}) e^{i,j,k} \end{aligned}$$

this is the discrete version of the curl from vector calculus.

Can't resist one more...

Next compute

$$\begin{aligned} d^2 f &= \sum_{i,j,k} (f_j - f_i + f_k - f_j) e^{i,j,k} \\ &= \sum_{i,k} (f_k - f_i) \sum_j e^{i,j,k} \\ &= 0 \end{aligned}$$

This is zero because we enforce $G^2 = 0$, which means

$$\sum_j e^{i,j,k} = 0,$$

i.e. the sum of all paths of length 2 that start and end on the same vertices must be zero.

David Egolf (Nov 15 2023 at 21:21):

That does indeed look fun! To understand what you're saying, I've been trying to understand what $Gf$ means.

$G$ is the sum of the arrows of our digraph $D$. So, $G = \sum_{(i,j) \in D}e(i,j)$ where $e(i,j)$ denotes the arrow from vertex $i$ to vertex $j$. $f$ is a $\mathbb{C}$-weighted linear combination of the vertices, I believe, so $f = \sum_{k \in D}f(k) e(k)$ where $k$ ranges over the indices of all the vertices in $D$, and $f(k) \in \mathbb{C}$, and $e(k)$ is the $k_{th}$ vertex of the digraph $D$.

David Egolf (Nov 15 2023 at 21:25):

I want to try computing $Gf$. To do this, we use the following multiplication between arrows and vertices: $e(k,l)e(i) = \delta(i,l)e(k,l)$.
We want to compute $Gf = \left(\sum_{(i,j) \in D}e(i,j) \right) f$.
I assume that we have the distributivity needed so this becomes:
$=\sum_{(i,j) \in D}e(i,j)f = \sum_{(i,j) \in D}e(i,j) \left( \sum_k f(k)e(k) \right)$
I assume that this multiplication of arrows distributes over vertices:
$=\sum_{(i,j) \in D}\sum_k e(i,j) f(k) e(k)$
I assume also I can move the complex number $f(k)$ around in the product $e(i,j)f(k)e(k)$ without changing the result:
$=\sum_{(i,j) \in D}\sum_k e(i,j) e(k) f(k)$

David Egolf (Nov 15 2023 at 21:29):

Using our multiplication rule, we get:
$=\sum_{(i,j) \in D} \sum_k \delta(j,k) e(i,j)f(k)$
The sum over $k$ only has one nonzero term for a given value of $j$. In this term, $k=j$.
So our sum becomes:
$Gf=\sum_{(i,j) \in D} e(i,j)f(j)$

Eric Forgy (Nov 15 2023 at 21:33):

(as I realize in panic that I wrote something incorrectly above which might well have confused you :scream: )
This first equality here is not correct

$$\begin{aligned} de^{i,j} &= G e^{i,j} -e^i G e^j + e^{i,j} G \\ &= \sum_k \left(e^{k,i,j} - e^{i,k,j} + e^{i,j,k}\right) \end{aligned}$$

Instead, it should just be

$$\begin{aligned} de^{i,j} &= \sum_k \left(e^{k,i,j} - e^{i,k,j} + e^{i,j,k}\right) \end{aligned}$$

Sorry about that if it caused confusion :pray:

David Egolf (Nov 15 2023 at 21:39):

Based on your checkmarks, I'm glad to know that I'm following along up to this point!
I hadn't looked carefully at the equality you just mentioned a fix for, but thanks for fixing it!
(I hope to think about this a bit more later, but for now I'm going to take a break.)

Eric Forgy (Nov 15 2023 at 22:11):

Awesome! It makes me happy to see someone working through this. I think it is fun and I've put it to good use through the years (including my current startup).

You got the algebraic expression for $G f$ correct, but there is also a neat intuitive intepretation. $G f$ picks out the values of $f$ at the ends of each edge and assigns them to the respective edge.

Similarly, $f G$ picks out the values of $f$ at the beginnings of each edge and assigns them to the respective edge.

Hence,

$$\begin{aligned} df &= Gf - fG \\ &= \sum_{(i,j)\in E} \left[f(j) - f(i)\right] e(i,j) \end{aligned}$$

It might be a little easier to see by just looking at one edge $e(i,j)$ and a function $f$. Here we have

$$e(i,j) f = f(j) e(i,j)$$

and

$$f e(i,j) = f(i) e(i,j).$$

One of the main themes here is that discrete 0-forms and discrete 1-forms do not commute whereas in the continuum, they do. This source of noncommutativity is not a flaw. Rather, it has been very powerful and I can't help think that it relates more accurately to nature than the continuum / commutative counterpart (which I consider as an approximation to a true finitary underlying spacetime).

In regular calculus, when you are taking an integral

$$\int_a^b f dx,$$

you never think about whether this should be writen that way or rather

$$\int_a^b dx f$$

because in the contuum limit, it doesn't matter (as long as $f$ is not stochastic). In a finitary universe, it does matter.

The noncommutativity of discrete 0-forms and discrete 1-forms can give rise to stochastic processes, which is how I connected this work to finance, where stocks and other assets are assumed to follow a geometric Brownian motion.

When a process is stochastic and you're defining integration, it matters whether you evaluate a function at the begining of an interval or the end (or anywhere in between). This is the source of Ito vs Stratonovich integration. Here is a good, fairly high-level, explanation of the difference:

• Itô and Stratonovich; a guide for the perplexed

People working in finance generally use the Ito representation. People working in physics generally use the Stratonovich representation.. Of course, you can map back and forth between them :blush:

David Egolf (Nov 16 2023 at 20:13):

Thanks for the intuitive explanation of $fG$ and $Gf$!

I can now see how $Gf-fG$ is like a gradient! Looking at the equation, $Gf- fG = \sum_{(i,j) \in D}(f(j) - f(i))e(i,j)$, I can see that $Gf-fG$ is basically a weighted sum of the arrows in our digraph $D$, where the weight for each arrow $e(i,j)$ is the change in $f$ as we move from the source vertex $i$ to the target vertex $j$ for that arrow. So we are keeping track of "how fast" $f$ is changing when you take a step along an arrow from one vertex to another!

This is all slowly starting to make sense. :smile:

Eric Forgy (Nov 16 2023 at 20:39):

Zactly :blush:

The intuition around curl is a little less obvious, but equally cool imo.

If we look at the simplest 2-diamond

i ----->----- j
|             |
v             v
|             |
k ----->----- l

then we can explicitly write a general discrete 1-form as

$$\alpha = \alpha(i,j) e(i,j) + \alpha(j,l) e(j,l) + \alpha(i,k) e(i,k) + \alpha(k,l) e(k,l)$$

and we have

$$\begin{aligned} G\alpha &= \alpha(j,l) e(i,j,l) + \alpha(k,l) e(i,k,l) \\ &= \left[\alpha(k,l) - \alpha(j,l)\right] e(i,k,l) \end{aligned}$$

since $e(i,j,l) = -e(i,k,l)$.

SImilarly,

$$\begin{aligned} \alpha G &= \alpha(i,j) e(i,j,l) + \alpha(i,k) e(i,k,l) \\ &= \left[\alpha(i,k) - \alpha(i,j)\right] e(i,k,l). \end{aligned}$$

Bringing it together, we have

$$\begin{aligned} d\alpha &= G\alpha + \alpha G \\ &= \left[\alpha(i,k) + \alpha(k,l) - \alpha(j,l) - \alpha(i,j)\right] e(i,k,l) \end{aligned}$$

which is what you get by performing a line integral around the diamond following the closed path

$$i\to k\to l\to j\to i.$$

This is the discrete "curl".

Finally, we can write a general discrete 0-form on this 2-diamond as

$$f = f(i) e(i) + f(j) e(j) + f(k) e(k) + f(l) e(l)$$

with

$$df = \left[f(j) - f(i) \right] e(i,j) + \left[f(l) - f(j) \right] e(j,l) + \left[f(k) - f(i) \right] e(i,k) + \left[f(l) - f(k) \right] e(k,l)$$

and it is straightforward to show that

$$d^2 f = 0$$

i.e. the "curl of a gradient is always zero".

Eric Forgy (Nov 16 2023 at 20:44):

Another thing...

Recall that we enforce $G^2 = 0$ which imposes relationships among "paths". We can see this on this simple 2-diamond by explicitly writing

$$G = e(i,j) + e(j,l) + e(i,k) + e(k,l)$$

so that

$$G^2 = e(i,j,l) + e(i,k,l) = 0 \implies e(i,j,l) = -e(i,k,l).$$

David Egolf (Nov 17 2023 at 17:46):

Very cool to see the discrete "curl" in your illustration above!

Based on your examples, and from reading the paper mentioned above, I think I now get how the "multiplication" works. I believe we have $e(i_1, i_2, \dots, i_n)e(j_1, j_2, \dots, j_m) = \delta(i_n, j_1)e(i_1, i_2, \dots, i_n, j_1, j_2, \dots j_m)$. Basically, if the path in our digraph written on the left ends where the path written on the right starts, we get a longer path by doing the first path and then the second path. But if these two paths aren't compatible in this way, then we get zero.

The $d$ operator is still a little bit scary-looking, but I think we define it using a sort of inductive setup. First we define $df = Gf - fG$, for any "zero form" $f$ (a $\mathbb{C}$-weighted sum of graph vertices). Then we can repeatedly apply the "Leibniz rule" to figure out what $d$ of higher order forms is.

I can now start to appreciate the stuff you're saying about the simpler form for $d$, and how this relates to constraints on $G$. And I guess that the constraint $G^2=0$ then indicates certain constraints on the graph structure. (Presumably this is where the diamond graphs come from? That is, they are the ones on which $G^2=0$?)

David Egolf (Nov 17 2023 at 17:54):

To elaborate slightly on the last point, we are given the below expressions for $d$ of certain 1-forms and 2-forms here:
d of certain forms

We notice that the middle terms have $\rho^2$ in them. I believe that $\rho$ is the notation this paper uses for what we are calling $G$. So, if $G^2=0$, all those middle terms go away.

Eric Forgy (Nov 17 2023 at 18:58):

Very cool that you looked up some of the earlier work by D&MH. They are awesome :raised_hands:

The best place to start from zero with this stuff is an article by Mueller-Hoissen that is no longer online at the original site, but thankfully, I preserved a copy on the nLab:

• Introduction to Noncommutative Geometry of Commutative Algebras and Applications in Physics

One way to get comfortable conceptually with $d$ is to think about its dual $\partial$, i.e. the boundary operator.

If you think of $s(i,j,k)$ as an oriented triangle (2-simplex) with

$$s(i,j,k) = s(j,k,i) = s(k,i,j) = -s(i,k,j) = -s(j,i,k) = - s(k,j,i)$$

and $s(i,j)$ as a directed edge (1-simplex) with

$$s(i,j) = -s(j,i)$$

the boundary is given by

$$\partial s(i,j,k) = s(j,k) - s(i,k) + s(i,j).$$

Note how this is an alternating sum of edges obtained by removing an index from the original simplex with the sign determined by the position of the index being removed.

For a general $p$-simple $s(i_0,\cdots, i_p)$, you have

$$\partial s(i_0,\cdots,i_p) = \sum_{r=0}^p (-1)^r s(i_0, \cdots , \hat{i_r} , \cdots , i_p)$$

where $\hat{i_r}$ means "remove the $r^{th}$ index".

$d$ is doing the dual thing. It is inserting indices in an alternating sum

$$d s(i_0, \cdots, i_p) = \sum_{i_r = 0}^p \left[ s(i_r, i_0, \cdots, i_p) - s(i_0, i_r, i_1, \cdots, i_p) + \cdots - (-1)^p s(i_0, \cdots, i_p, i_r) \right].$$

Now, the "boundary of a boundary is zero" is one of the most beautiful and profound pieces of mathematics with implications throughout physics. For example, in electromagnetic theory, "boundary of a boundary is zero" leads to charge conservation. Examples are limitless :blush:

Even more profound, imo, is the "coboundary of a coboundary is zero", i.e. $d^2 = 0$, but they are mostly just an expression of the same thing (with the word "same" being loaded especially on this chat :blush: ).

(Continued...)

Eric Forgy (Nov 17 2023 at 19:06):

Now... I spent a LONG time in grad school trying to get all this to work on simplices in a practical setting, and by "practical", I mean I can write code and generate numerical results of interest to engineers. My PhD was in computational electromagnetics after all :sweat_smile:

I got fairly far on my own, but it turns out simplices were not the right structure. I was missing diamonds :sweat_smile: I got far enough to convince Urs that this was worth looking into, he got excited for a few weeks and discovered that diamonds were somehow "special" in this formulation and I've been trying to catch up since then. He got more done in a couple weeks than I did in my entire PhD program :sweat_smile:

I've been trying to both explain and extend this for the past 20 years (on and off when I can spare some time from the day job, family, etc.).

I've generated enough numerical results based on this that I think I've proven its usefulness, but I hate publishing so all my results are scattered across blog posts and discussion forums :sweat_smile:

Eric Forgy (Nov 17 2023 at 19:14):

mexico.pdf
Let me upload a copy of this beautiful paper here too to reduce the chance it gets lost.

Eric Forgy (Nov 17 2023 at 19:17):

Eric Forgy said:

mexico.pdf
Let me upload a copy of this beautiful paper here too to reduce the chance it gets lost.

Looking at this again, I notice (and love), how MH ended his proofs with a heart symbol " :hearts:" :blush:

David Egolf (Nov 17 2023 at 19:20):

Thanks again for your long and interesting response!

I'm planning to take a break from this over the weekend, but hopefully I can come back to it and give your response a proper thoughtful read at that time.

I appreciate the link to the article. By looking at papers that cite this paper, I also found a couple other interesting resources. I first found this paper, which pointed me to this and this. I'm not sure how strongly related these are the topic of this thread, but I always am pleased to learn about the existence of an area of mathematics I was unaware of!

Eric Forgy (Nov 17 2023 at 19:25):

Yes. I have collected all of their papers and probably most references over the years. Of them all, I still recommend starting with the Mexico paper by Meuller-Hoissen. It is simple and pure. Like any research effort spanning several years (decades!), their papers evolved and are not entirely consistent (especially notations), but the ideas are beautiful throughout.

David Egolf (Nov 17 2023 at 19:32):

By the way, I'm starting to get ideas about how to describe some parts of this setup using some concepts from category theory :upside_down:. I'm not sure how useful this would be, but it's kind of fun to think about!

One thing that catches my attention about this setup is that we have things (e.g. vertices, arrows, sequences of arrows) that have certain positions (a starting vertex and an ending vertex - at least for sequences of arrows) and that we have a couple ways to "combine" these things:

1. When one path (a sequence of arrows) "flows into" another path (so the end of one is the start of the other), we can compose them to get a longer path. For example, we can compute $e(i,j)e(j,k) = e(i,j,k)$.
2. We can write sums of these things even if they don't connect nicely. For example, we have the term $e(i,j) + e(k,l)$ even if $j \neq k$.

So we have two ways of combining the arrows (at least) of our digraph.

Recently, I've been recently learning a little bit about monoidal categories. In monoidal categories, we have two ways to combine morphisms: intuitively in series and in parallel. So I start wondering if maybe there is a monoidal category lurking here, where the the arrows of our digraph (or perhaps sequences of composable arrows in our digraph) are the morphisms!

JR (Nov 17 2023 at 20:25):

https://en.wikipedia.org/wiki/Monoidal_category#Free_strict_monoidal_category

Eric Forgy (Nov 17 2023 at 20:28):

With your help, David, and with JR watching over us, I feel some real hope that we can crack this :blush:

Jean-Baptiste Vienney (Nov 17 2023 at 20:58):

How I would put order into this is by saying that:

• starting from a diamond graph $G$, and a commutative ring $R$, I form the path algebra $RG$. This is described on the wikipedia page Quiver (mathematics). They take $R$ to be a field but you can take any ring (but let's suppose it is commutative). It is defined like this:
• Call a path something of the form $e_1...e_n$ where the $e_i$ are edges such $e_1:a_1 \rightarrow a_2$, $e_2:a_2 \rightarrow a_3$ etc... ie. we can properly compose them. You also have an empty path $1_v$ for every edge $v$.

Jean-Baptiste Vienney (Nov 17 2023 at 20:58):

• $RG$ is the set of formal linear combinations $\lambda_1.p_1+...+\lambda_p.r_p$ where $\lambda_i \in R$ and the $p_i$'s are paths.
• The product is defined by composing paths and setting $p.q=0$ if $p$ and $q$ are not composable.
• $RG$ is in this way a $R$ algebra ie. it is a ring with a ring homomorphism $R \rightarrow RG$ (the unit is a bit tricky, look on the wikipedia page, it works only if the graph as finitely many edges).

Jean-Baptiste Vienney (Nov 17 2023 at 21:00):

• As a $R$-algebra, $RG$ is in particular a $R$-module (like a $k$-vector space but where $k$ is replaced by any ring, but takes $R$ a field if you prefer).

Jean-Baptiste Vienney (Nov 17 2023 at 21:01):

• So I can form the exterior algebra $\Lambda (RG)$ of $RG$. It will be composed of the linear combinations of elements of the form $p_1 \wedge ... \wedge p_n$ where the $p_i$'s are paths and $p_{\sigma(1)} \wedge ... \wedge p_{\sigma(n)} = (-1)^{sgn(\sigma)} p_1 \wedge ... \wedge p_n$ for every permutation $\sigma \in \mathfrak{S}_n$, ie. $\Lambda (RG)$ is a graded-commutative algebra.

Jean-Baptiste Vienney (Nov 17 2023 at 21:04):

• Then you could define $d:\Lambda(RG) \rightarrow \Lambda(RG)$ and verify that it gives you a differential graded commutative algebra.

Eric Forgy (Nov 17 2023 at 22:30):

Hi Jean-Baptiste. I appreciate your thoughts :pray: I wish it was that easy though :sweat_smile:

What you outline looks similar to the road Scott Wilson (student of Dennis Sullivan) took.

There is something of a "no-go" theorem that says, roughly speaking (the only way I know how), that you cannot construct a differential graded algebra on a finite space like this that is both (skew)commutative and associative. By anti-symmetrizing the product like that, you are sacrificing associativity, which imo is a bigger sin than giving up skew commutativity.

In our case, the noncommutativity is not a bug. It is an important feature.

Eric Forgy (Nov 17 2023 at 22:37):

For reference:

• https://golem.ph.utexas.edu/string/archives/000298.html#c000624
• https://golem.ph.utexas.edu/string/archives/000298.html#c000676
• https://golem.ph.utexas.edu/category/2007/02/infinitely_categorified_calcul.html#c007612
• https://golem.ph.utexas.edu/category/2007/02/infinitely_categorified_calcul.html#c007683

JR (Nov 18 2023 at 14:58):

Jean-Baptiste Vienney said:

• Then you could define $d:\Lambda(RG) \rightarrow \Lambda(RG)$ and verify that it gives you a differential graded commutative algebra.

Pretty sure this is related to path cohomology (aka GLMY cohomology).

JR (Nov 18 2023 at 15:09):

Dimakis and Mueller-Hoissen invented it though.

Patrick Nicodemus (Nov 18 2023 at 15:15):

Eric Forgy said:

Thanks you, everyone :pray:

Let's give the kind of directed graph I am interested in, i.e. those with no intermediate edges and no opposites, a name:

Definition: A diamond graph (not to be confused with this) is a directed graph with:

• No intermediate edges, i.e. if (i,j) is a edge from i to j, and (j,k) is an edge from j to k, then there is no edge (i,k)
• No opposite edges, i.e. if (i,j) is an edge, then (j,i) is not an edge
• No self loops, i.e. (i,i) is not an edge

Eric this seems like an interesting notion. Have you figured out what kind of posets you can capture this way? For example you cannot capture the poset of real numbers or another poset which is "dense". If we can capture a poset in this way we can capture one of its sub posets I think, so analogously to "forbidden graphs" in graph theory there are forbidden subposets that can block the whole poset from being a graph. An example of a forbidden poset is the ordinal $\omega+1$ or the opposite of $\omega+1$.
Are these examples sufficient, i.e. is every poset either a diamond graph or contains an embedded copy of $\omega+1$ or its opposite?

It should be able to capture every finite poset.

Patrick Nicodemus (Nov 18 2023 at 15:29):

If we can capture a poset in this way we can capture any of its sub posets I think
Actually now that I think about this it's less obvious. It seems like it should be true but the proof probably requires some care.

Patrick Nicodemus (Nov 18 2023 at 15:29):

Is a diamond graph structure on a given poset unique?

Jean-Baptiste Vienney (Nov 18 2023 at 17:09):

You said that this kind of discrete differential calculus has applications in finance. Could you give some pointers to that?

Eric Forgy (Nov 18 2023 at 18:20):

Patrick Nicodemus said:

Eric this seems like an interesting notion. Have you figured out what kind of posets you can capture this way?

Hi Patrick. Thank you for your interest :pray:

No. I haven't really looked into questions like that. I am like a gunslinging cowboy when it comes to this stuff :sweat_smile: I tend to put my head down and just calculate stuff, or more precisely, build models that that allow the calcultion of stuff.

Taking a cue from causal set theory though, I would imagine what I'm working on applies to locally finite posets.

For example you cannot capture the poset of real numbers or another poset which is "dense".

Right. Real numbers are not locally finite.

If we can capture a poset in this way we can capture one of its sub posets I think, so analogously to "forbidden graphs" in graph theory there are forbidden subposets that can block the whole poset from being a graph. An example of a forbidden poset is the ordinal $\omega+1$ or the opposite of $\omega+1$.

I have no idea about ordinals or forbidden graphs :sweat_smile:

Are these examples sufficient, i.e. is every poset either a diamond graph or contains an embedded copy of $\omega+1$ or its opposite?

No idea, but this sounds very cool and exactly why I am rambling about this stuff here, so that people like you might see something worthwhile. This definitely sounds worthwhile to look into :pray:

It should be able to capture every finite poset.

This would be super cool because this would capture the set (collection?) of viable discrete spacetimes. It would be important in my work as well as that of people working in causal set theory.

Is a diamond graph structure on a given poset unique?

If you are given a locally finite poset, as I've learned from JR, it's transitive reduction is a diamond graph (or Hasse diagram) and I'm pretty sure it is unique.

Having said that, I think these diamond graphs are more fundamental than posets because you need the diamond structure to build discrete differential geometry. The diamond also generates the poset. More people think about posets than diamonds, though :sweat_smile:

Patrick Nicodemus (Nov 18 2023 at 18:37):

@Eric Forgy By $\omega$ I just mean the natural numbers $\mathbb{N}$ together with their standard ordering. So $\omega =(\mathbb{N}, <_{\mathbb{N}})$. By $\omega+1$, I mean the standard natural numbers $\mathbb{N}$ together with a special additional element, say $\infty$, such that $n<\infty$ for each natural number $n$.
So, this poset cannot be regarded as a "diamond graph". I am conjecturing that every poset is either a diamond graph or contains an embedding of this poset (or its opposite)

Patrick Nicodemus (Nov 18 2023 at 18:40):

I will point out that there are examples of posets which are not locally finite but are diamond graphs. For example, let $I$ be an infinite set, and have an extra element $\top$ which is greater than everything in $I$, and $\bot$ which is less than everything in $I$, but every two elements of $I$ are incomparable.
This is not locally finite because $[\bot,\top]$ is infinite.
But it should be expressible as a diamond graph if I understand correctly.

Eric Forgy (Nov 18 2023 at 19:23):

Jean-Baptiste Vienney said:

You said that this kind of discrete differential calculus has applications in finance. Could you give some pointers to that?

Oh! Be caareful what you ask for :cowboy:

The first article I wrote on the subject can be found here:

• Noncommutative Geometry and Stochastic Calculus: Applications in Mathematical Finance, May 2002

I am pretty sure I can claim to be the first one to ever apply noncommutative geometry to finance :blush:

There is a section (2.9) on discrete stochastic calculus in my paper with Urs:

• Discrete Differential Geometry on Causal Graphs, July 2004

Shortly after that, I (self) published the first paper applying discrete (noncommutative) stochastic calculus to a practical problem in mathematical finance, i.e. pricing a derivative using a "discrete" Black-Scholes formulation:

• Financial Modelling Using Discrete Stochastic Calculus

Shortly after that, my CV ran across the desk of an actual mathematician (studied under Ross Street) working at a large (largest) asset manager who had read my papers. 21 interviews (with the same asset manager) later, I disappeared into the corporate world of finance and asset management, had kids, and life took over. I still tried to keep one foot in the research to keep my sanity though.

A couple years later, the global financial crisis hit and that made life "interesting". I was just getting my sea legs so started my blog to have a place to vent.

From there, I started writing a bit about discrete differential geometry in the hopes of cleaning it up and turning it all into a book someday. Here is a collection of articles:

• Network Theory and Discrete Calculus

In a nutshell, a binary tree is a particularly simple kind of 2-diamond. If you assign discrete coordinate 0-forms $x$ and $t$ to the binary tree with spacing $\Delta x$ and $\Delta t$, you can work out the commutative relations (see, e.g. this):

$$\begin{aligned} [dx,x] &= \frac{(\Delta x)^2}{\Delta t} dt \\ [dt,t] &= \Delta t dt \\ [dx,t] &= [dt,x] = \Delta x dx \end{aligned}$$

The main observation is that there are two distinct continuum limits you can consider here. For one, you can consider

$$\Delta x = c \Delta t, \Delta t \to 0$$

for some constant $c$. In this case, all the commutative relations vanish and you end up with the standard exterior calculus (in the limit). Because this limit results in the standard exterior calculus, I refer to the discrete case (with finite $\Delta t$) as "discrete exterior calculus".

The cool thing about this from a practical scientific computing perspective is that any model that involves exterior calculus can be robustly "discreteized" merely by reinterpreting the continuum forms as discrete forms and any model that converges with continuum forms is guaranteed to converge when using discrete forms because the mathematical framework itself converges. I call this a "meta algorithm". It is an algorithm for generating algorithms and takes all the typical choices that plague traditional numerical analysis away from you.

The more fun, in my opinion, continuum limit is

$$\Delta t = (\Delta x)^2, \Delta x \to 0.$$

In this case, one of the commutative relations survives even in the continuum, i.e.

$$[dx,x] = dt$$

There is a funny story here about how Urs and I independently came up with this, but Dimakis and Mueller-Hoissen beat us both to it long before. As far as I know, D&MH were the first to recognize you can derive stochastic calculus from noncommutativity with no measure theory in sight! :exploding_head:

Similar to exterior calculus, since we can obtain stochastic calculus from the continuum limit, I refer to the discrete case (with finite $\Delta t$) as "discrete stochastic calculus".

Any stochastic PDE that converges in the continuum can be cast as a discrete stochastic equation and it automatically contructs a converging numerical algorthm for you free of choices. It is a meta algorithm.

I tried to shy away from using too much heavy math jargon, but these concepts also permeate the practical work I am currently doing:

• Discrete Calculus for DeFi Math

I refer to "Node Functions" and "Edge Functions", which are really just discrete 0-forms and discrete 1-forms.

Jean-Baptiste Vienney (Nov 18 2023 at 19:46):

Thank you very much ahah.

Eric Forgy (Nov 18 2023 at 20:03):

Warning: Highly speculative thoughts ahead...

What I am going to say here ranks me pretty high on John's infamous crackpot index :sweat_smile:

What if, somehow, discrete exterior calculus and discrete stochastic calculus, were important? What if they did describe something about the foundations of the universe? If they did, we can't have two different continuum limits. What if these two calculi were related somehow?

The two calculi would correspond, i.e. be the same, if the following two formulas were consistent:

$$\sigma = \frac{(\Delta x)^2}{\Delta t}$$

and

$$c = \frac{\Delta x}{\Delta t}.$$

Combining them, we have

$$\sigma = c^2\Delta t = c \Delta x.$$

This would imply some kind of "Planck diffusion" :sweat_smile:

If you have a few drinks (or maybe smoke a special herb), it is fun to think about this.

David Egolf (Nov 20 2023 at 17:36):

Ah, I think I understand your analogy between then boundary operator and the $d$ in our case (which is more like a "coboundary" operator). That's pretty cool! I find it interesting that our $d$ takes us "up a dimension" (e.g. from vertices to arrows), while the boundary operator takes us "down a dimension" (e.g. from arrows to vertices).

Do you happen to know if we can define a "boundary" operator for paths in our digraphs of interest? As a first try, I wonder if we could modify the formula you gave above (which was for simplices):
$\partial e(i_0,\dots,i_p) = \sum_{r=0}^p (-1)^r \left( e(i_0, \dots,i_{r-1}) + e(i_{r+1}, \dots, i_p) \right)$ where the $r_{th}$ term in the sum on the right side omits the $r_{th}$ vertex in our original path. So we get a sum where we have a pair of paths in each term.

If we can do this, it might be fun to see what the boundary of the coboundary is.

David Egolf (Nov 20 2023 at 17:41):

On a different topic, I'm still trying to understand what it means to have $G^2=0$ for a digraph. Consider the digraph $D=1 \to 2 \to 3$. I think this is a diamond graph, but when I compute $G^2$ I don't get zero!

To illustrate, we first recall that $G = \sum_{(i,j) \in D} e(i,j)$. In this case, $G=e(1,2) + e(2,3)$. Now we can compute $G^2$. We get: $(e(1,2) + e(2,3))(e(1,2) + e(2,3)) = e(1,2,3)$.

So, if $G^2=0$, we need that $e(1,2,3)=0$! So I start to think that it takes a bit more data than our digraph $D$ to really get something where $G^2=0$: we also need to say something about how $e(1,2,3)=0$, I think.

JR (Nov 20 2023 at 18:00):

David Egolf said:

Ah, I think I understand your analogy between then boundary operator and the $d$ in our case (which is more like a "coboundary" operator). That's pretty cool! I find it interesting that our $d$ takes us "up a dimension" (e.g. from vertices to arrows), while the boundary operator takes us "down a dimension" (e.g. from arrows to vertices).

Do you happen to know if we can define a "boundary" operator for paths in our digraphs of interest? As a first try, I wonder if we could modify the formula you gave above (which was for simplices):
$\partial e(i_0,\dots,i_p) = \sum_{r=0}^p (-1)^r \left( e(i_0, \dots,i_{r-1}) + e(i_{r+1}, \dots, i_p) \right)$ where the $r_{th}$ term in the sum on the right side omits the $r_{th}$ vertex in our original path. So we get a sum where we have a pair of paths in each term.

If we can do this, it might be fun to see what the boundary of the coboundary is.

If you use $e(i_0, \dots,i_{r-1}, i_{r+1}, \dots, i_p)$ instead of $e(i_0, \dots,i_{r-1}) + e(i_{r+1}, \dots, i_p)$ you get path (aka GLMY) homology.

JR (Nov 20 2023 at 18:05):

Actually, I should mention that you get path/GLMY homology if you take a suitable restriction of this map. You need to restrict to images that actually correspond to paths in the digraph.

Jason Erbele (Nov 21 2023 at 00:50):

David Egolf said:

On a different topic, I'm still trying to understand what it means to have $G^2=0$ for a digraph. Consider the digraph $D=1 \to 2 \to 3$. I think this is a diamond graph, but when I compute $G^2$ I don't get zero!

To illustrate, we first recall that $G = \sum_{(i,j) \in D} e(i,j)$. In this case, $G=e(1,2) + e(2,3)$. Now we can compute $G^2$. We get: $(e(1,2) + e(2,3))(e(1,2) + e(2,3)) = e(1,2,3)$.

So, if $G^2=0$, we need that $e(1,2,3)=0$! So I start to think that it takes a bit more data than our digraph $D$ to really get something where $G^2=0$: we also need to say something about how $e(1,2,3)=0$, I think.

This is a directed graph with no intermediate edges, no opposite edges, and no self-loops, so it satisfies the definition of a diamond graph Eric Forgy gave here. So I think we are confused together.

As an aside, @Eric Forgy, you mentioned binary trees earlier. When I looked at your link, I encountered something very different from what I thought binary trees were.....

Jason Erbele (Nov 21 2023 at 01:02):

I haven't dealt too much with binary trees, specifically, but my understanding in the undirected graph case is that they are trees (undirected connected graphs with no cycles) that have vertices with only one incident edge (leaves) and "internal" vertices that have exactly three incident edges, and one of the leaves can be declared to be the root.

I have not dealt at all with directed binary trees, so my naive assumption was that you would have the shape of an undirected binary tree, but all the arrows would either point toward or away from the root. The mismatch between this and what you are calling binary trees could be due to my ignorance, but it certainly surprised me.

Eric Forgy (Nov 21 2023 at 01:47):

David Egolf said:

On a different topic, I'm still trying to understand what it means to have $G^2=0$ for a digraph. Consider the digraph $D=1 \to 2 \to 3$. I think this is a diamond graph, but when I compute $G^2$ I don't get zero!

To illustrate, we first recall that $G = \sum_{(i,j) \in D} e(i,j)$. In this case, $G=e(1,2) + e(2,3)$. Now we can compute $G^2$. We get: $(e(1,2) + e(2,3))(e(1,2) + e(2,3)) = e(1,2,3)$.

So, if $G^2=0$, we need that $e(1,2,3)=0$! So I start to think that it takes a bit more data than our digraph $D$ to really get something where $G^2=0$: we also need to say something about how $e(1,2,3)=0$, I think.

I said enforcing $G^2 = 0$ imposes constraints. In this case, you have discovered that the graph

$$1\to 2\to 3$$

is one dimensional, i.e. has no 2-diamonds :blush:

Eric Forgy (Nov 21 2023 at 01:57):

To add a bit more, the only possible 2-cell (or 2-path) that would make sense on $1\to 2\to 3$ is $e(1,2,3)$, but $G^2=0$ says that $e(1,2,3)=0$ so there are no 2-diamonds and the graph is 1-dimensional.

Imposing $G^2 = 0$ gives rise to dimensionality.

Think about a 2-dimensional checkerboard with all edges directed in such a way to imply a flow across the diagonal.

If you compute $G^2$ on this directed graph and force it to be zero, you find that there are no 3-diamonds, but there are nonzero 2-diamonds, so this graph is 2-dimensional.

Recall what I said here.

Eric Forgy (Nov 21 2023 at 02:02):

Jason Erbele said:

As an aside, Eric Forgy, you mentioned binary trees earlier. When I looked at your link, I encountered something very different from what I thought binary trees were.....

You are right. I was being sloppy. I should have said "binomial tree". Sorry about that :sweat_smile:

David Egolf (Nov 21 2023 at 02:14):

I think I understand how setting $G^2=0$ imposes certain equations between paths in a digraph $D$. (And that's pretty cool! The idea that there is a connection to dimension is intriguing...)

I'm currently wondering why we require our digraphs to be diamond graphs, if we need to add in more restrictions later to ensure $G^2=0$ anyways. I thought the constraints of "no intermediate edges, no opposite edges, and no self-loops" were primarily to ensure that $G^2=0$. But now I see that even with those constraints being met, we still need to impose additional equations to ensure $G^2=0$. So I'm guessing that the reason for these constraints ("no intermediate edges, no opposite edges, and no self-loops") is perhaps a bit more subtle, or maybe for a slightly different reason(?).

Eric Forgy (Nov 21 2023 at 02:18):

It might be worth being super explicit here. Let's go back to the directed graph:

i ----->----- j
|             |
v             v
|             |
k ----->----- l

You can verify that we have

$$G^2 = e(i,k,l) + e(i,j,l)$$

and forcing this to be zero implies that

$$e(i,k,l) = -e(i,j,l)$$

but what does that mean???

This means $e(i,k,l)$ and $e(i,j,l)$ are not really paths anymore. They are equivalence classes of paths that can be interpretted as an oriented 2-dimensional surface, i.e. a 2-diamond :blush:

We are constructing higher-dimensional spaces from 1-dimensional directed graphs by imposing $G^2 = 0$.

Eric Forgy (Nov 21 2023 at 02:21):

So I'm guessing that the reason for these constraints ("no intermediate edges, no opposite edges, and no self-loops") is perhaps a bit more subtle, or maybe for a slightly different reason(?).

TL;DR: This is required in order to construct discrete spacetimes from directed graphs that support a discrete form of differential geometry :blush:

David Egolf (Nov 21 2023 at 02:24):

Heh, when I see that drawing, I helplessly start thinking about "the right hand rule". When I "curl the fingers of my right hand along the path $e(i,k,l)$", my thumb points out of the screen. When I "curl the fingers of my right hand along the path $e(i,j,l)$", my thumb points toward the screen. So if we think as the "thumb directions" as specifying vectors normal to the screen, the vector induced by $e(i,k,l)$ is the negative of the one induced by $e(i,j,l)$.

Eric Forgy (Nov 21 2023 at 02:25):

Your intuition is serving you well. That is exactly what you should be thinking of and gets back to that "curl" calculation we did earlier :blush:

David Egolf (Nov 21 2023 at 02:34):

This is rather vague, but I'm reflecting on the following:

• Our multiplication defined on vertices and paths creates higher dimensional (longer) paths from lower dimensional ones
• Our $G^2=0$ condition imposes certain equations on the structure (algebra?) generated by these paths. We want to interpret these equations as having some kind of geometrical content.
• So we end up with a (potentially infinite) collection of kinds of geometrical objects: points, paths of length 1, paths of length 2, paths of length 3, etc.
• And paths of shorter length can fit inside paths of the longer length
• And there are certain equations relating paths of the same length to one another

To recap all this:

• We have things of increasing dimension, with relationships to one another, and relationships among things of the same dimension
• We want to start thinking about geometrical concepts inspired by these things

Eric Forgy (Nov 21 2023 at 02:35):

Tantalizing isn't it? Makes you think of n-categories :cowboy:

David Egolf (Nov 21 2023 at 02:43):

This starts to remind me of the concepts of "simplicial set" and "globular set".

A simplicial set is a functor from $\Delta^{op}$ to $\mathsf{Set}$, where $\Delta$ is the simplex category. A functor $F: \Delta^{op} \to \mathsf{Set}$ associates some additional data (a set) to each kind of object in $\Delta$.

A globular set is a functor from $\mathbb{G}^{op}$ to $\mathsf{Set}$, where $\mathbb{G}$ is the globe category.

Both the simplex category and the globe category consist of a bunch of objects (which I think we can think of as being of "increasingly higher dimension") and some morphisms that describe how objects of different dimension relate to one other. At least in the case of the globe category we also add in some equations that describe how these morphisms have to relate to one another.

I wonder if there is some category $C$ so that every functor $F: C \to \mathsf{Set}$ (or possibly to another, more "geometric" category) can provide one of the structures that you are interested in.

Eric Forgy (Nov 21 2023 at 02:49):

I can't resist saying one more thing about our friend the 2-diamond.

i ----->----- j
|             |
v             v
|             |
k ----->----- l

There is one nonzero 2-diamond that can be written as either $e(i,k,l)$ or $-e(i,j,l)$ since both represent the same 2-diamond. So the space of discrete 2-forms is one dimensional, i.e.

$$\beta = \beta(i,k,l) e(i,k,l).$$

There is a special discrete 2-form called the "volume form"

$$vol = vol(i,k,l) e(i,k,l).$$

Consider the discrete 1-form

$$\star e(i,k) = vol(i,k,l) e(k,l).$$

If we multiply $e(i,k)$ and $\star e(i,k)$ we get

$$\begin{aligned} e(i,k)\star e(i,k) &= vol(i,k,l) e(i,k,l) \\ &= vol. \end{aligned}$$

Eric Forgy (Nov 21 2023 at 02:49):

If you take a discrete $p$-form $\alpha$ and multiply it by a discrete $(n-p)$-form $\beta$ and it results in the volume form (in $n$ dimensions), then we can write

$$\beta = \star \alpha$$

and $\star\alpha$ is the dual of $\alpha$ and $\star$ is referred to as the "discrete Hodge star".

Eric Forgy (Nov 21 2023 at 02:51):

The discrete Hodge star was the elusive holy grail I spent 6 years of grad school looking for and Urs found it in a couple of exciting weeks :blush:

David Egolf (Nov 21 2023 at 03:23):

Very cool! (Although I think I don't know enough about to the usual Hodge star operator to really appreciate what you just shared).

I'm still working on learning more about things in this direction. My current approach is to do some reading in "Smooth Manifolds and Observables". (I'm not sure how far I'll get, but it's a fun read so far!) So I may or may not learn cool things from that book which would be relevant to the discussion here :upside_down:.

Eric Forgy (Nov 21 2023 at 04:01):

The funny thing, to me anyway, is that you don't need all that fancy higher math to understand what I'm doing. This could potentially become the way to teach these concepts :blush:

Jason Erbele (Nov 21 2023 at 06:11):

If you lengthen each path in our favorite 2-diamond by one ($i \to j \to k \to n$ one the one hand and $i \to l \to m \to n$ on the other hand), the condition $G^2 = 0$ seems to indicate all four of the two-edge paths equal zero: $e(i,j,k) = e(j,k,n) = e(i,l,m) = e(l,m,n) = 0$. Does that mean this hexagon is merely 1-dimensional, as far as diamond graphs are concerned?

Eric Forgy (Nov 21 2023 at 08:33):

Apparently, yes :blush:

If $G^2 = 0$, we must also have

$$e(p) G^2 e(r) = \sum_{q} e(p,q,r) = 0$$

so the sum of all 2-paths that begin and end at the same vertex must be zero. In the hexagon, there is only one 2-path connecting any two points, so that one 2-path must be zero meaning all 2-paths are zero so the hexagon is one-dimensional.

Eric Forgy (Nov 21 2023 at 08:50):

The smallest 2-diamond is the one we've already drawn with two 2-paths conecting $i$ and $l$.

A cube with directed edges from one corner to the oppposite corner across the major diagonal is an example of a non-vanishing 3-diamond, but there is a smaller one than that.

Challenge: Can you find it? What does it look like? :blush:

Note: A 3-diamond is bounded by 2-diamonds.

Jason Erbele (Nov 21 2023 at 10:02):

I suppose the directed hypercubes would give a family of non-vanishing n-diamonds, where the diamond dimension matches the usual dimension. As for your challenge, I think I found two examples that are both smaller than a directed cube (in both edge count and vertex count) – I'm not confident I completely understand the diamond dimension, so either of my examples might be off by one dimension, though I doubt both would be. I will give David a chance to play with the puzzle before I show my hand.

David Egolf (Nov 21 2023 at 17:48):

Eric Forgy said:

The smallest 2-diamond is the one we've already drawn with two 2-paths conecting $i$ and $l$.

A cube with directed edges from one corner to the oppposite corner across the major diagonal is an example of a non-vanishing 3-diamond, but there is a smaller one than that.

Challenge: Can you find it? What does it look like? :blush:

Note: A 3-diamond is bounded by 2-diamonds.

(Thanks for giving me a chance to try out the puzzle, Jason!)

If we have a nonzero 2-diamond, I think we have a digraph where $G^2=0$ means that we have equations relating different paths of length 2 (those having two arrows).

So, by a nonzero 3-diamond, I believe we mean a digraph where $G^2=0$ means that we have equations relating different paths of length 3.

David Egolf (Nov 21 2023 at 17:48):

To get such equations, let's look at the consequences of $G^2=0$. If this is true, then in particular $e(i,j)G^2=0$ for every arrow $e(i,j)$ in our digraph. I think $G^2$ is the sum of all the length 2 paths in our digraph. So then $e(i,j)G^2=0$ is the sum of all length 3 paths having as their first arrow $e(i,j)$.