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: How to express constraints in presheaf-based models?

Peva Blanchard (Oct 08 2025 at 14:21):

Consider the category $C$ with two objects $V,E$ and two non-identity arrows $V \xrightarrow{s,t} E$. Then a graph can be described as a presheaf $G : C^{op} \to \text{Set}$. In particular, we obtain a category ${\cal G}$ of graphs.

However, for a graph theorist, $G$ is more likely described as a directed multigraph possibly with self-loops. The usual graph our graph theorist has in mind usually involves more constraints. For the sake of simplicity, just consider the constraint stating $(\alpha)$ that there is at most one edge between any two vertices.

Now, say I want to describe this data structure with presheaves. I see, at least, two options:

1. I can just select the presheaves on $C$ which satisfy condition $(\alpha)$. I obtain a collection ${\cal G}(\alpha)$ of presheaves. But now it is not clear, at first sight, that we obtain a category (we need to work to check, e.g., if the ${\cal G}$-morphisms are compatible with $(\alpha)$).

2. Or maybe I can change the base category $C$ for another category $D$. Something like two objects $V, E$ and an epi $V \times V \twoheadrightarrow E$. And selecting only presheaves that preserve some stuff (e.g. products, epi to mono, ...)

Maybe there are other ways I am missing.

My question is: are there typical and nice ways to express constraints like $(\alpha)$ in a presheaf-based model? By nice, I mean, for instance, that some general results apply to produce an actual category ${\cal G}(\alpha)$.

Kenji Maillard (Oct 08 2025 at 14:52):

You could restate $(\alpha)$ using an [[orthogonality]] condition (see section orthogonality of morphisms to objects).

Consider the two following graphs $I = v_0 \to v_1$ with two vertices and a single edge (the walking edge) and $D$ with 2 vertices $v_0, v_1$ as well and two parallel edges $e_0, e_1 : v_0 \to v_1$ between these vertices. Let $\iota : I \to D$ map the unique edge of $I$ to $e_0$. Now given a graph $G$, $\mathrm{Hom}(I, G)$ is the set of edges of $G$ while $\mathrm{Hom}(D, G)$ is the set of parallel pairs in $G$. Precomposition by $\iota$ induces a restriction

$$\iota^* : \mathrm{Hom}(D, G) \to \mathrm{Hom}(I, G)$$

and this map is invertible exactly when $G$ has no distinct pair of parallel edges. This is exactly stating that $G$ is (right) orthogonal to $\iota : I \to D$.

Ryan Wisnesky (Oct 08 2025 at 15:01):

We usually start from a presentation of a category rather than a category, so you can literally write down equations you want to hold in your category. But certain classes of constraint, like an arrow being mono, will go beyond equational presentations.

Damiano Mazza (Oct 08 2025 at 15:41):

Just a remark concerning your particular example: "simple" directed graphs (in the sense of graphs with at most one edge $a\to b$ between any two nodes $a,b$) may be expressed as [[separated presheaves]] on the coverage saying that the two arrows $v\to e$ are a covering family. While this does not generalize to obtain more sophisticated constraints that you may have in mind, it does tell us that the category of simple directed graphs is a [[quasitopos]] (a potentially interesting side remark).

James Deikun (Oct 08 2025 at 15:51):

That's not just a potentially interesting side remark, it's a very important point. There are various ways of expressing constraints like this, but they all tell you something important about what the resulting category is like.

James Deikun (Oct 08 2025 at 15:53):

Another important point is that when you have constraints that only eliminate objects, there is no chance of ending up with something that isn't a category. It's only when you start eliminating arrows that that can happen.

Peva Blanchard (Oct 09 2025 at 05:52):

Thank you all for your answers. I didn't know about these concepts, I'll try to work them out on a few other cases.

Peva Blanchard (Oct 09 2025 at 21:43):

So, I tried to practice a bit by considering another property: $(\beta)$ the source and target of every edge are distinct (aka no self-loops).

My attempts to reuse a technique based on orthogonality, or presheaf separation, didn't work.
But I think that's because property $(\beta)$ differs from $(\alpha)$ in the sense that $(\alpha)$ somehow that asserts that two things are equal (uniqueness), whereas $(\beta)$ asserts that two things are distinct.

Morgan Rogers (he/him) (Oct 10 2025 at 07:02):

Moreover, note that if the domain of a graph homomorphism satisfies beta then this need not be the case for its codomain (this can be used to prove that indeed it cannot be capture by right orthogonality, I think)

Nathan Corbyn (Oct 10 2025 at 07:11):

One hack is to introduce a self loop at every vertex and then assert that all self loops are equal—i.e., replace ‘no self loops’ with ‘no non-trivial self loops’

Nathan Corbyn (Oct 10 2025 at 07:13):

(Beware the notion of homomorphism this induces is very wonky)

Morgan Rogers (he/him) (Oct 10 2025 at 15:31):

I originally started typing something along the lines of Nathan's comment, but the homomorphism thing is important: without self-loops you cannot identify vertices (so you only get graph homs which are injective on vertices) whereas with unique self-loops more graph homomorphisms are possible.

Peva Blanchard (Oct 11 2025 at 07:48):

It is interesting to see how the naive picture of a graph can get subtle when formalizing its details.

John Baez (Oct 11 2025 at 11:54):

The naive picture of a graph is very vague. There are many different kinds of graphs depending on various choices you can make:

• are edges directed or undirected?
• can there be an edge from a vertex to itself? If so,
  • does each vertex have a specified 'identity edge' from it to itself?
• can there be more than one edge from one vertex to another? If so,
  • is there a set of edges from one vertex to itself or just a number of them?

I think this gives $2 \times 3 \times 3$ definitions of graph, and I'm probably leaving out some important choices.

John Baez (Oct 11 2025 at 11:55):

There are also other choices, a bit less common, like:

• given a directed edge from $v$ to $w$ is there an operation that lets you turn it around and get a directed edge from $w$ to $v$?

I've used this feature when studying topological crystals, for example. They'd also be good for electrical circuits, where you want to have a direction on each wire so the current flowing along the wire is a real number - but you can change your mind about the direction of the wire, and then that number changes sign.

Peva Blanchard (Oct 16 2025 at 09:18):

John Baez said:

I've used this feature when studying topological crystals, for example.

The link to your website is broken, but I found your paper on the arxiv here

John Baez (Oct 16 2025 at 13:46):

Thanks. By the way, if people don't copy a broken link when telling someone that a link is broken, that person can fix all copies of that link. But we can't fix other people's comments!

In this case I forgot that the paper is called crystal.pdf, not crystals.pdf, so here's a working link:

http://math.ucr.edu/home/baez/crystal.pdf

This version may be slightly newer than the arXiv version: I forget.

Elisha Goldman (Oct 16 2025 at 18:05):

This might not get to the core of the question, but here are some ways to define different categories of graphs pretty efficiently, and I think you can generalize some of the lessons here. Since you're working with presheaves, you can talk about the cardinality of the sets to define conditions like $(\alpha)$. Commutation conditions generally have to be described by limits, but a lot of the time they can be incorporated into the structure, like how the property of every edge-set being symmetric can be rolled up into an opposition morphism, and the same with group inverses.

Peva Blanchard (Oct 17 2025 at 07:51):

Thank you, this is very useful. It is interesting how the author combines all the topics discussed here (full subcategory of presheaf categories, adapting the base category, and orthogonality).