Maths - Category Theory Graphs

A step up in complexity from a category of sets we can look at the category of graphs.

Objects in Grf are a collection of vertices and edges related in certain ways. However category theory tends not to look inside objects.
Morphisms in Grf sends vertices to vertices and edges to edges, such that, if a->b is an arrow then F a -> F b is an arrow. Again category theory tends not to look inside these morphisms.
Relating category theoretic view to set theory view. There is a representable object in Grf (see Yoneda lemma page). This might help us relate the internal and external views of Grf. This representable object is a graph with two vertices and an arrow between them. Arrows into this object can be thought of as picking out all the edges in the other object. This gives a homset with an arrow for each edge.
Given a morphism 'F' between two graph objects. If both these objects have hom functors to the representable object then there is a function 'f' between these two sets. This function goes in the opposite direction.

It is easier to see this contravarience from this diagram.

If 'F' is given we can derive 'h' from 'g' by composing with 'F' but we can't derive 'g' from 'h'.

So if we want to get the usual functions in set we need to start with Grf^op

Grf^op

Objects in Grf^op are the same as the objects in Grf.

Morphisms in Grf^op go in the opposite direction to the morphisms in Grf. So this time:

if F a-> F b is an arrow
then a -> b is an arrow.

In Grf these functions can be surjective or injective as with set.	surjective function
	injective function
In Grf^op these arrows can be the reverse of these.

So this embedding is given by:

h_X = hom_C(_,X) : Grf ^op-> Set

Internal View

Although category theory does not tend to look inside objects it is helpful to relate this to a more set theoretical approach.

The objects in Grf consist of a set together with some internal structure.

Directed Graph

Two functions, source and target) from the set of edges to the set of vertices.

graph arrow diagram
Two functions, between the source and target objects, which respect the graph structure.

An example of a functor category.

These maps between the source and target imply functors of the verticies and edges. So what does it mean for the arrows to respect the graph structure? For instance, if we look inside the functions, the diagram on the right is valid.
If we look at parts of this arrow we see: edges map to edges
Where the vertex function is surjective edges may be reduced to a loop.
Both the vertex function and the edge function may be injective.

Functors Between Graphs

Lets look at the possible diagrams for graphs.

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

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.

	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.
	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:

	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.
	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'