School of Computing Research Colloquia

Generalizing relations from sets to graphs

John Stell, Knowledge Representation and Reasoning Research Group

A relation on a set can be visualized as a collection of arrows going between dots which represent the elements of the set. One key operation on relations is taking the converse -- this corresponds reversing the direction of all the arrows. Another operation is taking the complement (or negation) of a relation. It is possible to have relations on (undirected) graphs rather than sets. Visually these have arrows between the edges and nodes of the graph (subject to some restrictions). For these relations we cannot take converses or complements, but each of these operations has two weaker forms giving four inter-related operations. This gives relations on graphs a more elaborate algebraic structure than the one based on Boolean algebras that we have for relations on sets.

In the talk I will explain why relations on sets are a continuing topic of research in computer science, and why relations on graphs are an exciting (and in some ways novel) generalization. There will be plenty of pictures to help visualize the structures involved.