# Graphs and quivers

## Graphs

We started with the intuition that geometry should be about states/places: \(\vert{x},\vert{y},\vert{z}\) and their transitions: \(\tde{\vert{x}}{\vert{y}}{\card{a}}\), \(\tde{\vert{y}}{\vert{z}}{\card{b}}\), etc. Evidently we have the main ingredients of a **graph**, specifically a **directed graph**:

The objects \(\vert{x},\vert{y},\vert{z}\) are called **vertices.** \(\tde{\vert{x}}{\vert{y}}{\card{a}}\) is a **labeled edge**, where \(\card{a}\) is the label, which we call a **cardinal**. The unlabelled form is written \(\de{\vert{x}}{\vert{y}}\). \(\vert{x}\) is called the **tail vertex** and \(\vert{y}\) is called the **head vertex** of the edge. When vertices represent states and edges represent transitions between states, we’ll use the terms vertex/state and edge/transition synonymously.

It turns out that we will have to consider specific *kinds* of directed graphs if we wish to build a notion of geometry. These graphs are **quivers**, also known as **directed multigraphs**, which are directed graphs that allow multiple edges as well as cycles between any pair of vertices:

## Cardinal quivers

A seemingly fundamental geometrical idea is that of a **direction**.

For discrete geometry, a direction will take the form of a label for an entire *set* of transitions: these are the transitions that, although they are between different pairs of vertices, are all in the same direction (in whatever sense). We’ll call this label a **cardinal**, by analogy with the cardinals of a compass \(\list{\card{N},\card{E},\card{S},\card{W}}\). We'll write cardinals in a typewriter font to distinguish them from symbols representing vertices, etc.

A **cardinal quiver** is a quiver with a set of (typically repeated) labels on the edges of the quiver, called **cardinals**, with the property of **local uniqueness**:

the list of cardinals on edges {entering, leaving} a given vertex cannot contain duplicates

For example, the situation \(\tde{\vert{y}}{\vert{x}}{\card{c}},\tde{\vert{y}}{\vert{z}}{\card{c}}\) is forbidden, as the cardinal \(\card{c}\) occurs twice when leaving \(\vert{y}\). In contrast, the situation \(\tde{\vert{x}}{\vert{y}}{\card{c}},\tde{\vert{y}}{\vert{z}}{\card{c}}\) is permitted, as \(\card{c}\) occurs entering \(\vert{y}\) once and leaving \(\vert{y}\) once. Some more examples of forbidden and permitted situations are shown below:

This uniqueness property has a very important purpose: it ensures that a pair of a vertex and a cardinal \(\tuple{\vert{v},\card{c}}\) will *unambiguously identify an edge* (if one exists), since there can only be one edge starting at \(\vert{v}\) that is labeled by \(\card{c}\). This corresponds to the basic requirements of the notion of a *direction*: it unambiguously identifies the navigational choices an agent should make. As a motivation: for "north" to be a direction, there cannot be *two ways to go north* from one location that lead to different locations.

Cardinal quivers will be our focus, so I’ll refer to them as **quivers** to avoid cumbersome language. If we need to refer to the *classical* notion of a quiver as a directed multigraph, we’ll use the term **unlabelled quiver**.

Since cardinals will almost always label multiple edges in a quiver, we will use color to represent the edges labeled by each cardinal, and choose cardinal letters e.g. \(\rform{\card{r}}\), \(\gform{\card{g}}\), \(\bform{\card{b}}\) to reflect these colors:

Here are more examples – since the arrowhead color indicates the name of the cardinal, we'll drop the legends. The cardinals label multiple edges, but still obey local uniqueness:

Note that the right-most example has some of the intuitive aspects of an actual discrete geometry: the cardinal \(\rform{\card{r}}\) can be taken (meaning a move in the direction \(\rform{\card{r}}\) can be made) for any of the states \(\vert{x},\vert{y},\vert{z}\). Taking \(\rform{\card{r}}\) repeatedly simply cycles through these states: a discrete analog of a circle.

For simplicity, we can depict quivers that contains multiple edges between the same vertices by combining the edges, using multiple arrowheads instead. Using this convention the first two quivers above look as follows:

## Enumeration

Since finite, connected quivers will play a major role in this series, it is interesting to enumerate all the finite connected quivers of a given size.

One way to organize this enumeration is in terms of what we’ll call **quiver skeletons**, which are undirected simple graphs (graphs without multiple edges between vertices) that serve as *templates* for quivers. We can enumerate these skeletons by fixing the number of vertices, then taking all possible sets of undirected edges between these vertices that include each vertex at least once and still produce a connected graph. We count these quiver skeletons up to graph isomorphism, in other words, the labeling of the vertices of these graphs is not significant.

Here is a gallery that shows the quiver skeletons for each vertex count:

The number of skeletons for \(n\) vertices is the sequence \(\{1,3,10,50,354,3883,...\}\), which is not yet in the Online Encyclopedia of Integer Sequences (OEIS), though I have submitted it.

Once we have chosen a particular skeleton, we can then go about attaching **cardinal structure** to it to turn it into a quiver (which recall means a *cardinal* quiver). Typically there are multiple possible choices, although there is an obvious symmetry we must take into account: we can perform any *global renaming* of cardinals and we’ll still have the same essential cardinal quiver. More generally, the action of the relevant symmetry group is the simultaneous relabeling of vertices, edges, and cardinals:

Here, the vertices have been rewritten \(\list{\rewrite{1}{2},\rewrite{2}{3},\rewrite{3}{1}}\) and the cardinals have been rewritten \(\list{\rewrite{\rform{\card{r}}}{\bform{\card{b}}},\rewrite{\bform{\card{b}}}{\rform{\negated{\card{r}}}}}\) – note the underbar on \(\rform{\negated{\card{r}}}\), which indicates we flip the cardinal direction when rewriting \(\bform{\card{b}}\) to \(\rform{\card{r}}\).

Let’s look at some examples of the quivers associated with skeletons. We’ll only visualize the cases involving 3 or fewer cardinals, since the number of quivers rapidly increases as a function of the number of cardinals.

Taking the skeleton on the first row, which is a one-vertex graph with a self-loop, there is exactly one possible quiver for a given number of cardinals:

These quivers are called **bouquet quivers**.

Taking the 2nd skeleton on the 2nd row as another example, there are 0 quivers with 1 cardinal, 3 quivers with 2 cardinals, and 9 quivers with 3 cardinals. (The ‘flat’ arrowheads below indicate that a cardinal is present in both orientations on that edge).

The numbers of quivers for this skeleton as a function of the number of cardinals is \(\{0,3,9,19,34,55,83,119,164,219,...\}\), with closed form \(6^{-1}n^3+2^{-1}n^2+3^{-1}n-1\).

For the 1st skeleton on the 2nd row, there are 2 quivers with 1 cardinal, 4 quivers with 2 cardinals, and 6 quivers with 3 cardinals:

The numbers of quivers for this skeleton as a function of the number of cardinals is \(\{2,4,6,9,12,16,20,25,30,36,42,49,...\}\), with closed form \(4^{-1}n^2+n+8^{-1}(7+(-1)^n)\).

For the 1st skeleton on the 3rd row, there is only 1 quiver with 1 cardinal, 16 quivers with 2 cardinals, and 64 quivers with 3 cardinals:

The numbers of quivers for this skeleton as a function of the number of cardinals is \(\{1,16,64,211,551,1276,2672,...\}\). No simple closed form is apparent, though one probably exists.

The following table summarizes the number of quivers that can be obtained from the skeletons with fewer than 4 vertices. The columns indicate skeletons, and the rows numbers of cardinals, and the entries indicate the number of quivers:

Only the first 3 columns of this table are in the OEIS.

The number of 5-cardinal quivers for the final 3 skeletons are too expensive to compute in a straightforward way, these are marked with a ? in the table.

Moving on to skeletons with 4 vertices, of which there are 50, we have this table:

Finally, by summing over the tables above, we can obtain a bird’s eye view that captures how many quivers there are as a function of number of vertices \(n\) and cardinals \(c\):

Clearly, beyond \(\sym{n} = 1\), even for modest values of \(\sym{c}\), we find our armory overflowing with quivers!