# reperiendi

## The category GraphUp

Posted in Category theory, Programming by Mike Stay on 2008 January 17

The category GraphUp of graphs and Granovetter update rules has

• directed finite graphs as objects
• morphisms generated by Granovetter rules, i.e. the following five operations:
• add a new node. (creation, refcount=0)
• given a node $x,$ add a new node $y$ and an edge $x\to y.$ (creation, refcount=1)
• given edges $x\to y$ and $x \to z,$ add an edge $y\to z.$ (introduction, ++refcount)
• remove an edge. (deletion, --refcount)
• remove a node and all its outgoing edges if it has no incoming edges. (garbage collection)

It’s a monoidal category where the tensor product is disjoint union. Also, since two disjoint graphs can never become connected, they remain disjoint.

Programs in a capability-secure language get interpreted in GraphUp. A program’s state graph consists of nodes, representing the states of the system, and directed edges, representing the system’s transitions between states upon receiving input. A functor from a program state graph to GraphUp assigns an object reference graph as state to each node and an update generated by Granovetter rules to each edge.