left and right euclidean;
Both category theory and graph theory study patterns based on diagrams consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists.
By a simple graph, we mean a set equipped with a symmetric reflexive relation . Morphisms between simple graphs are functions which preserve the given relations. Elements of are called vertices. Write to say .
When drawing graphs, we put an edge between vertices , iff and . In particular, we will not bother drawing an edge between and itself; we can think of it as tacitly there if we like. Perhaps better yet, that tacit edge can be thought of as a path of length from to itself (and who bothers drawing a path of length ?). In any case, it is clear that there is a natural bijection between
simple graph structures on in the graph-theorist’s sense (i.e., graphs that are undirected, loop-free, and with at most one edge between two vertices), and
reflexive symmetric relations on ;
thus we are within our rights to identify these two concepts.
This then includes natural operations like edge contractions as quotients. Namely, if is a morphism as defined above, and if we have and , we still have by default, so we can think of as contracting the edge between and in down to an edge of length between and itself in .
The category of simple graphs is denoted by .
The category has very good properties. For example,
See for example Adamek and Herrlich.
reflects monos and epis (because is faithful).
It follows that both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in . For instance:
In , the pushout of any mono is a mono.
Suppose we have a pushout diagram in :
Since preserves both pushouts and monos, and since the pushout of a mono in is a mono, we have that is monic in . Since reflects monos, this means is monic in .
If are maps in , then their equalizer is given at the vertex level by
and at the edge level by ; in other words, if belong to and there is an edge between them in , then that edge lies in . To express this last condition, we say the subgraph is full (at the edge level).
Thus, is a regular mono in iff both is monic in and is full at the edge level.
The coequalizer of and , say , is given at the vertex level by
and at the edge level by taking the image of the composite , so that
Thus, is a regular epimorphism if it is surjective at both the vertex and edge levels.
The category of simple graphs has a ternary factorization system as follows: each morphism factors as
is a surjection between vertex-sets and at the edge level, i.e., is a regular epi;
induces an identity between vertex-sets (hence is jointly monic and epic), but without necessarily being full at the edge level;
is given by an injection between vertex-sets and is full at the edge level, and (thus) is a regular mono.
The factorization of into followed by is the (regular epi)-mono factorization, while the factorization of into followed by is the epi-(regular mono) factorization. To round out the discussion, we prove that regular monos are stable under pushout (which ensures that the epi-(regular mono) factorization is an orthogonal factorization system).
In , the pushout of any regular monomorphism along any map is a regular mono.
Let be a regular mono in , and let be any map. Form the pushout of the pair as a coequalizer diagram
where , are the coproduct inclusions. We are trying to show that is a regular mono. Certainly is monic in (again since preserves monos and pushouts), so we just have to check that is full at the edge level. So, suppose ; we must show . According to how we form coequalizers , there exist such that , , and . Since and are embedded disjointly in their coproduct, we have that
either both and belong to the -component, in which case and (but in that case we’re done because follows from , according to how the coproduct is constructed);
or both and belong to the -component. But according to how pushouts are constructed at the vertex level, this means there exist such that , and , . Since , or , and is full at the edge level (because it is a regular mono), we have , and therefore or , as desired.
is co-regular, i.e., is regular.
This is obvious from the first definition of “regular” given here.