Maths - Concrete Category - Graphs

As a next step up from a category of sets we can now look at the category of graphs. The objects in Grf consist of a set together with some internal structure.

Graphs also happen to represent category theory diagrams so perhaps we can find a way to relate the internal structure of graph objects to the category theory relationship of objects and arrows.

Category diagram for Graph

The category diagram for graph has two objects: a set of nodes and a set of edges. There are two arrows giving the source and target node for each edge. category diagram for graph

Functors Between Graphs

First lets look at the diagrams for graphs..

  External diagram Internal mapping for a specific example
category diagram: endomap external endomap internal
simpler diagram which we can use in the case of endomaps: endomap external endomap internal

An endomap is a mapping from a object to itself. A category diagram for this case is shown in the higher row in the table above, we can see that it is an endomap because both the domain and the codomain are labled 'A', and hence are the same.

However, because this is an endomap, we can simplify the diagram by showing 'A' as one object.

Graph Categories

So lets start with Grf, a category of graphs, these have a bit more structure than sets and so will allow us to explore the relationships between objects which are sets+structure. I find it helpful to adapt the diagrams as bit, to get us started, so that we can include some of the normally hidden structure beneath. This is just to get us started, we won't always do this as the nature of category theory is to abstract as much as possible. Lets start with sets, which are perhaps the simplest objects, because they don't have the structure of operations like multiplications and additions.

set category Sets may just be any set of elements, or some or all of these sets may themselves be sets (and these inner sets may also contain sets and so on). Also these elements may all have a common type or not. So we could show the structure inside the set instead of representing them as single characters.
group category In the case of structures like groups with a group operation then we could show that, perhaps by combining with a Cayley graph.

Arrows

I find that including this further information helps even more with arrows:

set arrow category Here I have showed individual arrows going from each element of the two objects rather than the more usual single arrow between the two objects.
group arrow category In the case of groups we may be able to give an indication of how the group operation is changed by the arrow.

We will call the object at the start of the arrow the 'domain' and the object at the end of the arrow the 'codomain'

Subcategories of Grf

Two important subcategories are idempotent and invertible endomaps:

idempotent endomap

Idempotent Endomap

All arrorw lead to fixed points.

invertable endomap

Invertible Endomap (permutation).

contains only 2-cycles and fixed points

Irriflexive Graphs

Endomaps (mappings from an object to itself) are related to two parallel maps between different objects.

  External diagram Internal mapping for a specific example
Irriflexive Graph: irriflexive external irriflexive internal
related endomap: endomap external endomap internal

The endomap is given by the difference between the red and blue mappings.

Adjunctions in Graphs

Adjunctions in Graphs

Adjunctions are described on page here.

Between reflexive graph and set.

In reflexive graph: every node has loop to itself.

graph example

reflexive graph

irreflexive

Between irreflexive graph and set.

In irreflexive graph: every node does not have loop to itself.

Between dynamical system graph and set.

In dynamical system graph: every node has one outgoing arrow.

dynamical systems graph
dynamical systems and fixpoints

Different dynamical system graph and set.

This time the morphism to set defines the fixpoints.

Monoid

If we overlay multiple graphs (shown in different colours) then we get a Cayley graph as discussed on this page. This gives us a way to move onto monoids and groups in terms of category theory on this page.


metadata block
see also:

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.