Learning Out Loud: C-Sets · learning: reading & references

Stream: learning: reading & references

Formally, a simple graph $G = (V, E)$ is a set of vertices $V$ equipped with an edge relation $E \subseteq V \times V$ for which:

$E(u, v)$ iff $E(v, u)$ .
$\neg E(v, v)$ .

( $u, v \in V$ ).

(Tangential comment: The edge relation is symmetric and irreflexive, whereas a partial order includes being reflexive and antisymmetric! Hm.)

In a simple digraph the symmetry axiom is dropped, so that the edges are directed. Graphs and digraphs are basic objects in discrete mathematics, are the source of fundamental data structures in computer science.

Despite this, the concept of a simple graph is often unsatisfactory for both theoretical and practical reasons. The category of simple graphs is badly behaved. Moreover, there is not a single concept of graph suitable for all applications, but rather that graphs belong to a rich family of related concepts.

For a category theorist, a graph $G$ consists of two sets, a vertex set $G(V)$ , and an edge set $G(E)$ , together with two functions $G(\text{src}), G(\text{tgt}) : G(E) \to G(V)$ . Define $e \bullet \text{src}$ as $G(\text{src}(e)$ and $e \bullet \text{tgt}$ as $G(\text{tgt}(e)$ . Thus, a graph is directed, may have multiple edges between two vertices, and may have loops, making it what a graph theorist would call a “multidigraph.”

In Catlab, the definition of a graph is captured by the schema:

using Catlab.CategoricalAlgebra

@present SchGraph(FreeSchema) begin
  V::Ob
  E::Ob
  src::Hom(E,V)
  tgt::Hom(E,V)
end

It appears that one can build a category in this language by stating the names of objects with ::Ob and the names of morphisms with ::Hom(X,Y).

Having defined the schema for graphs, the module Graphs in Catlab creates a Julia data type for graphs like this:

@acset_type Graph(SchGraph, index=[:src,:tgt])

It appears that this constructs an instance of the schema, though I’m not familiar with the @acset_type or index=[:src,:tgt] expressions.

Then there are some very nice code examples of how to define and visualize graphs in AlgebraicJulia.

Graphs are an example of a class of structures called $C$ -sets. $C$ -sets are defined relative to a small category $C$ . In this context, the category $C$ is interpreted as a schema, describing the kinds of parts in the structure and the subpart relations between them.

The author refers to maps

\text{src},\text{tgt}

as “subpart relations”, because they map an entity (an edge) to two things it implicitly has (a source and target).

The interpretation is that there are two kinds of parts, of type $V$ and $E$ . Parts of type $V$ have no subparts, while parts of type $E$ have two subparts of type $V$ called $\text{src}$ and $\text{tgt}$ .

Given a small category $C$ , a $C$ -set is a functor $X : C \to \textsf{Set}$ .

Going to sleep now, will continue in the morning.

Category Theory
Zulip Server
Archive

Stream: learning: reading & references

Topic: Learning Out Loud: C-Sets

Julius Hamilton (Aug 30 2024 at 02:59):