Lecture 36 - Categories from Graphs

John Baez · May 2018

In Section 3.2.1 of Seven Sketches - and please download today's new version of the book! - Brendan Fong and David Spivak describe a nice way to get categories from graphs. It's very simple, yet important for building databases.

Here's the basic idea. Start with a graph, for example this:

It has a bunch of "edges", like $f,g,h,i$, going between "nodes" like $A,B,C,D$. Then build a category where the objects are the nodes and the morphisms are the paths of edges. We compose morphisms by attaching one path onto the end of another.

For example $f$ is a path of length 1 from $A$ to $B$, so it gives a morphism $f: A \to B $. $h$ is a path of length 1 from $B$ to $D$, so it gives a morphism $g: B \to D$. We can compose these two morphisms and get $h \circ f : A \to D$, which is a path of length 2 from $A$ to $D$.

There's also another morphism from $A$ to $D$, namely $i \circ g : A \to D$.

In this example the longest paths have length 2, but in general a path could have any natural number as its length, including 0. Paths of length 0 are important because they give the identity morphisms in our category. For example, there's a path of length 0 from $A$ to $A$, which you can't see because it has no edges! It gives the identity morphisms $1_A: A \to A$.

When we build a category from a graph this way, it's called the free category on that graph. And if we call the graph $G$, we call the free category on that graph $\mathbf{Free}(G)$.

I should warn you that different people mean different things by "graph", depending on:

whether we put arrows on the edges,
whether we allow more than one edge going from one node to another,
whether we allow edges going from a node to itself,
whether the edges have names, and
whether we allow infinitely many nodes and edges.

But category theorists have a very specific thing in mind when we say "graph". We are very generous: we say yes to all these questions!

So, for example, we allow this graph:

This graph has just one edge. But the free category on this graph has infinitely many morphisms, namely $$ 1_z : z \to z $$ $$ s : z \to z $$ $$ s \circ s : z \to z $$ $$ s \circ s \circ s : z \to z $$ and so on. There's one morphism for each natural number. In fact, this is how category theorists often think about the natural numbers!

We also allow this graph:

Puzzle 104. How many paths of length $n$ go from $x$ to $x$ in this graph?

The answer is a famous sequence of numbers. So, you're getting a famous sequence from the free category on a graph!

It may sound complicated to let our graphs have so many features, but it's actually more complicated to disallow them. The category theorists' definition of graph is very simple:

Definition. A graph $G$ is a set $N$ of nodes, a set $E$ of edges, a function $s : E \to N$ assigning each edge its source, and a function $t: E \to N$ assigning each edge its target.

You can visualize the source and target of an edge using this picture:

but remember: it's possible to have $s(e) = t(e)$.

If you're a stickler for detail, you may also want to see the precise definition of a "path":

Definition. Given a graph, a path from a node $x$ to a node $y$ is a finite sequence of edges $(e_1, \dots, e_n)$ with

$$ s(e_1) = x, \quad t(e_1) = s(e_2), \quad \dots, \quad t(e_{n-1}) = s(e_n), \quad t(e_n) = y. $$ Here $n = 0, 1, 2, 3, \dots$ is called the length of the path.

Okay, I think that's enough for today! Next time we'll use this idea to think about databases. For now you should try these exercises, or at least look at other students' solutions:

Exercise 3. Show that $\textbf{Free}(G)$ really is a category.

Exercise 4. Completely work out the set of morphisms between each pair of objects in the category called $\textbf{3}$, which is

$$ \textbf{Free}( [ v_1 \overset{f_1}{\rightarrow} v_2 \overset{f_2}{\rightarrow} v_3 ] ) .$$ Exercise 5. The category $\textbf{3}$ is an example of a general idea. For each natural number $n$ there's a category $\mathbf{n}$ that works the same way. Figure out what it is, and figure out the total number of morphisms in this category!

And here's a puzzle for people who love numbers. I'll admit it: I love numbers. But math is not only about numbers, so if you don't love them, don't worry: this puzzle is not important for this course, though it is part of a big subject in math:

Puzzle 105. It's been known since at least the fifth century BC that $$ \sqrt 2 = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots\,}}}}} $$ If we cut off this continued fraction we get these rational approximations to $\sqrt{2}$: $$ \frac11, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots$$ where the denominator of the $n$th fraction in this list is called the Pell number $P_n$ and the numerator is $P_n + P_{n-1}$. Find a graph with two nodes $x$ and $y$ such that the number of paths of length $n$ from $x$ to $y$ is the $n$th Pell number.

To read other lectures go here.

Pierre Prado · May 2018

Ex 3). Objects - nodes - Ok -1. Morphisms - {f,h,g,i} -Ok -2. Identities - Ok -3. Associative feature also holds -4 - verified 1,2,3,4 true, then it´s a category. Preorder-no.. ok?

Keith E. Peterson · May 2018

Puzzle 104. How many paths of length $n$ go from $x$ to $x$ in this graph?

The answer is a famous sequence of numbers. So, you're getting a famous sequence from the free category on a graph!

When $n=0$, \[\lbrace id_x \rbrace, \\ 1, \] when $n=1$, \[\lbrace f \rbrace, \\ 1, \] when $n=2$, \[\lbrace f\circ f, g \circ h \rbrace, \\ 2, \] when $n=3$, \[\lbrace f\circ f\circ f, f\circ g \circ h, g\circ h\circ f \rbrace, \\ 3, \] when $n=4$, \[\lbrace f\circ f\circ f\circ f, f\circ f\circ g \circ h, f\circ g \circ h\circ f, g\circ h\circ f \circ f, g\circ h\circ g \circ h \rbrace, \\ 5,\\ \] when $n=5$, \[\lbrace f\circ f\circ f\circ f\circ f, f\circ f\circ f\circ g \circ h, f\circ f\circ g\circ h\circ f, f\circ g\circ h\circ f \circ f, \\ g\circ h\circ f\circ f\circ f, g\circ h\circ g\circ h\circ f, g\circ h\circ f\circ g\circ h, f\circ g\circ h\circ g \circ h \rbrace, \\ 8,\\ \cdots \]

It's the old Fibonacci sequence.

Jonathan Castello · May 2018

Keith wrote:

It's the old Fibonacci sequence.

Yep. One way to see this is as a dynamical system: state $x$ represents adult rabbits, and state $y$ represents newborn / immature rabbits. With a single step of the system, all mature rabbits remain mature; mature rabbits spawn one newborn rabbit each; and any existing newborn rabbits become mature.

Well, this is the story I learned from The Number Devil, at any rate.

John Baez · May 2018

Right! Let's spell it out: a path $\gamma: x \to x$ of length $n \ge 2 $ must either be of the form $ f \circ \delta$ for some path $\delta : x \to x$ of length $n-1$, or of the form $ h \circ g \circ \delta $ for some path $\delta : x \to x$ of length $n-2$. So, if $F_n$ is the number of paths of length $n$, we must have

$$ F_n = F_{n-1} + F_{n-2} $$ for $n \ge 2$, but also it's easy to see $F_0 = F_1 = 1$. Fibonacci!

Another way to say it is that the Fibonacci number $F_n$ counts the number of ways to write $n$ as an ordered sum of 1's and 2's. For example

$$ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 $$ so the fourth Fibonacci number is 5.

MatthewDoty · May 2018

Puzzle 105. This is a great question.

Here's my quick stab at an answer:

John Baez · May 2018

By the way, Keith, you're writing $g \circ h$ to mean "do first $g$ and then $h$", while most category theorists - and in particular me - use it to mean "do first $h$ and then $g$", just as we do for functions, where

$$ (g \circ h) (x) = g(h(x)) . $$ I mention this just because it's possible to get very confused when different people are using different systems without knowing it.

Computer scientists sometimes use $g ; h$ to mean "do first $g$ and then $h$", and that's a nice notation where the first thing comes first yet we don't get confused.

Keith E. Peterson · May 2018

Yeah, I noticed that after the fact.

We'll just say we're working with the opposite category because flipping all those morphisms is a lot of work.

John Baez · May 2018

Or, we could say you redefined "$g$" to mean "$h$", and vice versa. :)

Jonathan Castello · May 2018

Keith said:

We'll just say we're working with the opposite category because flipping all those morphisms is a lot of work.

John said:

Or, we could say you redefined "$g$" to mean "$h$", and vice versa. :)

Hey, this category is isomorphic to its dual! :D

MatthewDoty · May 2018

@John

By the way, Keith, you're writing $g \circ h$ to mean "do first $g$ and then $h$", while most category theorists - and in particular me - use it to mean "do first $h$ and then $g$", just as we do for functions, where
$$ (g \circ h) (x) = g(h(x)) . $$

So... I have been trying to write up how to use Lawvere's fixed point theorem to prove Gödel's second incompleteness theorem as per our discussion.

In Lawvere's 1969 paper I think he used the opposite convention for composition :

Taking the case $X = 1$, one has that every $f : A \to Y$ gives rise to a unique $ \ulcorner f \urcorner : 1\to Y^A$ and that every $1 \to Y^A$ is of that form for a unique $f$. Since for every $a : 1\to A$ one has (dropping the indices $A$, $Y$ on $\epsilon$ when they are clear) \[ \langle a, \ulcorner f\urcorner \rangle = a.f \] one calls the “evaluation” natural transformation; note however that we do not assume in general that $ f$ is determined by the knowledge of all its “values” $a.f$

(the above is from page 4)

It's confusing!

Keith E. Peterson · May 2018

Can any strictly increasing monotonic sequence of natural numbers be created from length concatenation of edges of a graph? If not, what is a counterexample?

Fredrick Eisele · May 2018

@KeithEPeterson I presume you mean...

Puzzle 104+. Given an arbitrary connected graph having a node labeled 'x', how many paths of length 'n' go from 'x' to 'x' in that graph? Where the resulting function $ H: \mathbb{N} \rightarrow \mathbb{N} $ is used to produce a sequence. For which sequences is it possible to construct a graph which encodes the sequence?

Edit: Make the question more general

Edit: Make it a puzzle

Edit: Strike monotonic

Edit Stated another way... Given a function as defined above... $$ J : \textbf{Graph} \rightarrow ( \mathbb{N} \rightarrow \mathbb{N} ) $$ Does $J$ have an inverse? Does $J$ have a right adjoint? $$ J^{-1} : ( \mathbb{N} \rightarrow \mathbb{N} ) \rightarrow \textbf{Graph} $$

Keith E. Peterson · May 2018

Are you making a puzzle, Fredrick?

Fredrick Eisele · May 2018

@KeithEPeterson I thought I was restating your puzzle. Generating graphs that encode monotonically increasing functions on the natural numbers sounds interesting.

Keith E. Peterson · May 2018

I wasn't really making a puzzle, but conjecturing out loud.

Though, you should make that into a puzzle.

Edit: The reasoning I'm thinking out loud is because every strictly increasing monotonic sequence of natural numbers has an associated real number attached to it (Beatty sequences).

It would, therefore, stand to reason that if every such sequence also has a graph, that we could then associate to each graph the real number that's associated to each sequence.

John Baez · May 2018

Matthew wrote:

It's confusing!

It's not very confusing, because he is deliberately using the nonstandard notation $a . f$ to mean "do first $a$, then $f$". That's just a variant of the computer scientist's $a ; f$. It only gets very confusing when people use $a \circ f$ to mean "do first $a$, then $f$", because 99.5% of mathematicians use it to mean "do first $f$, then $a$".

I'll admit to having been one of the 0.5%. But that was when I was young and didn't choose my battles wisely!

Jonathan Castello · May 2018

Keith wrote:

Can any strictly increasing monotonic sequence of natural numbers be created from length concatenation of edges of a graph? If not, what is a counterexample?

I have a hunch that the sequence must have a strictly increasing derivative (well, divided difference) everywhere. For instance, every sequence $p_i = 1, 3, 4, \cdots$ is unobtainable, since in order to go from one null path to three unit-length paths, you must have three self-loops on the start vertex. The next step would multiple those three unit-length paths into nine length-two paths.

EDIT: Strictly increasing, not positive. Positive derivative just means monotonic function; I expect that the derivative itself needs to be monotonic, too, as a necessary (but perhaps insufficient) condition.

John Baez · May 2018

Fredrick puzzled:

Is there a graph for every possible monotonic sequence?

No, there's not one for

$$ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, \dots $$ I leave it as a puzzle to figure out why!

I don't think "monotonic" is especially relevant here. For example, it's pretty easy to find graphs where the number of paths from $x$ to $x$ goes like

$$ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, \dots $$ or

$$ 1, 0, 0, 2, 0, 0, 4, 0, 0, 8, 0, 0, 16, 0, 0, \dots $$

Jonathan Castello · May 2018

John wrote:

$$ 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, \dots $$

Aha -- rose graphs! (Except each petal has its own vertex, rather than all petals being self-loops.)

EDIT: You added more zeroes when I refreshed. :(

John Baez · May 2018

Sorry, I decided to add more zeros, just to spice it up! Both sequences describe the number of paths of length $n$ for some graph.

Pierre Prado · May 2018

Considering fibonacci - golden ratio relation, is it possible to devise a explict connection/translation between the puzzle 104´s graph and the x²=1+x equation?

MatthewDoty · May 2018

Considering fibonacci - golden ratio relation, is it possible to devise a explict connection/translation between the puzzle 104's graph and the x²=1+x equation?

Here's my attempt -

Assume you want to compute the number of paths of length $n$, starting from $x$. You can start counting by taking one of two paths:

Go along $f$, and end up at $x$. Then count the number paths of length $n - 1$
Go along $h \circ g$, and end up at $x$ again. Then count the number of paths of length $n - 2$.

Let $f_n$ be the number of paths. Then

\[ f_n = f_{n-1} + f_{n-2} \tag{★} \]

Now consider

\[ \phi := \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \]

With (★) we have

\[ \begin{align} \phi & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \\ & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1} + f_{n-2}}{f_{n-1}} \\ & = \underset{n \to \infty}{\mathrm{lim}} \left(1 + \frac{f_{n-2}}{f_{n-1}} \right) \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-2}}{f_{n-1}} \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1}}{f_{n}} \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \left(\frac{f_{n}}{f_{n-1}}\right)^{-1} \\ & = 1 + \left(\underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}}\right)^{-1} \\ & = 1 + \phi^{-1} \\ \end{align} \]

Hence $\phi = 1 + \phi^{-1}$. Now multiply both sides by $\phi$. This gives:

\[ \phi^2 = \phi + 1 \]

...as you wanted to see...

David Lambert · May 2018

Puzzle 105: I can't see Matthew's answer in comment #5, so I will write my own. Following what John wrote in comment #4, it seems like it should be sufficient to add an arrow $k$ from $x$ to itself. That way, every path of length $n+2$ will come from composing either $f$ or $k$ with a path of length $n+1$, or composing $h\circ g$ with a path of length $n$. Since this gives the recurrence relation $$P_{n+2}=2P_{n+1}+P_n$$ that is satisfied by the Pell numbers (with $P_0=1$ and $P_1=2$ due to $\{\text{id}_x\}$ being the only path starting and ending at $x$ of length zero and $\{f\},\{k\}$ being the only paths of length one).

Generalizing slightly, one can get any recursion relation of the form $$a_{n+2}=\alpha a_{n+1}+\beta a_n\qquad\text{for }\alpha,\beta\in\mathbb{N}$$ by starting with the node $x$ and its identity arrow, and adding $\alpha$ arrows from $x$ to itself and $\beta$ nodes, each with a pair of arrows connecting each node to the node $x$ (restricting to the case with just two nodes, $x$ and $y$, one can get any $\alpha\in\mathbb{N}$ and square betas $\beta=m^2, \forall m\in\mathbb{N}$ with the appropriate arrows).

To every recursion relation with specified base case(s) there is associated a generating function. For example, for $$F_{n+2}=F_{n+1}+F_n\qquad\text{with }P_0=1,\,P_1=1$$ there is associated the generating function $$F(z)=\frac{1}{1-z-z^2},$$ which has the Fibbonacci sequence as the sequence of coefficients in its formal power-series expansion. Does the generating function associated with a graph tell us anything interesting about the graph?

David Lambert · May 2018

The sequence given by $a_0=1$, $a_1=0$, $a_{n+2}=4a_n$, i.e., $1,0,4,0,16,...,0,2^{n},0,2^{n+2},...$ can be obtained from either the graph with two nodes $x$ and $y$ with non-identity arrows $g,g':x\to y$, $h,h':y\to x$, or from the graph with five nodes $x$, $y_i$ where $i\in\{1,2,3,4\}$ and arrows $g_i:x\to y_i$ and $h_i:y_i\to x$.

Fredrick wrote:

$$ J : \textbf{Graph} \rightarrow ( \mathbb{N} \rightarrow \mathbb{N} ) $$ Does $J$ have an inverse? Does $J$ have a right adjoint?

Since there are cases where at least two graphs give the same sequence, J is not injective, so it cannot have an inverse.

MatthewDoty · May 2018

Following what John wrote in comment #4, it seems like it should be sufficient to add an arrow $k$ from $x$ to itself.

If you still can't see my diagram, you should know this is my solution (I didn't write the justification, though).

Anindya Bhattacharyya · May 2018

Re composition on the left or the right – there's a very neat approach to this in this textbook:

Berwick & Keating: Categories and Modules

The authors define two types of categories – right categories where f followed by g is written gf, and left categories where it is written fg. So every category has a "chirality" (left or right), and every functor can be co-chiral or contra-chiral. In particular we have a contra-chiral "mirror functor" that sends every category to its mirror (same objects, same arrows in the same direction, but composition is the other way round).

The motivation for this is they want to deal with bimodules over non-commutative rings, where one ring acts on the left and the other acts on the right. So they need to treat both conventions equally, and have a clean way of switching back and forth.

It took me a little time to understand why one might want to think of chirality as a structural feature of a category relating to how composition is defined, as opposed to a mere "matter of notation". But I do like the way it doesn't arbitrarily choose one convention as normal and the other as perverse.

And it fits with practical computer programming – many languages use both left and right composition (eg in JavaScript functions are written on the left foo(bar) while methods are written on the right bar.foo()).

Robert Figura · May 2018

The identity morphism is a path of length zero! For some reason I never tried to see it that way. Since all composites exist (say, because it's easy to check – proving that two paths commute is the hard part) I always thought of all links (conflating paths and arrows) as essentially having length 1. Which sort of works, too, but having paths and arrows separate like this is nice!

Regarding puzzle 104, hah, there's just one canonically famous sequence... However, I had to look twice to get rid of the feeling that things should get multiplied somehow.

It seems we should call these categories Fibonacci and Pell. Is that something people do?

John Baez · May 2018

Fredrick wrote approximately:

$$ J : \textbf{Graph} \rightarrow \mathbb{N}^\mathbb{N} $$ Does $J$ have an inverse? Does $J$ have a right adjoint?

(Here $\mathbb{N}^\mathbb{N} $ is my preferred notation for the set of functions from $\mathbb{N}$ to itself - that is, sequences of natural numbers

This is a great thing to think about. The questions as stated don't make sense, for two reasons. Both these problems can be fixed:

A. It is not a graph that gives a sequence of numbers, but a pointed graph: a graph with a chosen node. This lets us count the number of paths of length $n$ starting and ending at that node, and get a sequence of natural numbers. There is a category $\textbf{Graph}_\ast$ of pointed graphs, where a morphism is a map of graphs that sends the chosen node of one to the chosen node of the other.

B. $\textbf{Graph}_\ast $ is a category while $\mathbb{N}^\mathbb{N} $ is a mere set. Thus, it's not clear what $J$ should be: a functor (a map between categories) or a function (a map between sets). We can cure this problem in two equivalent ways:

Turn the category $\textbf{Graph}_\ast $ into a set, namely the set of isomorphism classes of pointed graphs.
Turn the set $\mathbb{N}^\mathbb{N} $ into a category with only identity morphisms.

Since they're equivalent we can use the first, less stressful approach.

There is indeed a well-defined function $J$ from the set of isomorphism classes of pointed graphs to the set of sequences of natural numbers, where we count the number of paths of length $n$ from the chosen node to itself.

This function $J$ is neither one-to-one nor onto. The interesting question are thus:

Which sequences of natural numbers arise by counting the number of paths of length $n$ from the chosen node in a pointed graph to itself?
When do two pointed graphs give the same sequence?

I know a nice answer to the first, which I'll explain if nobody can guess it, but I'm pretty clueless about the second.

I think Matthew Doty at least can guess the answer to the first question here, since he rapidly translated the Pell sequence into a pointed graph that gives it.

I think the easiest way to tackle the first question is to figure out a nice general formula for the number of paths of length $n$ from any node in a graph to any other node.

John Baez · May 2018

David Lambert wrote:

Does the generating function associated with a graph tell us anything interesting about the graph?

Yes! I may be confused, but I think generating function you're talking about is associated with a pointed graph, as explained in my comment above. Anyway, there's a field called algebraic graph theory that studies things like this.

Robert Figura · May 2018

John asked:

Which sequences of natural numbers arise by counting the number of paths of length n from the chosen node in a pointed graph to itself?

I'll consider a simpler graph: one that has distinct loops of lengths $a_1, ... a_k$. Then the number of paths with length $n$ that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients $b_i$ such that:

$n=\sum_i^k a_i \cdot b_i$

Edit: that's not good enough! See my discussion with John below.

I have no idea how to simplify that expression, but I claim it to be the answer to John's first question.

Regarding the second question, if two graphs give the same sequence then they contain the same kinds of loops and the same number of them. I have no proof for this at the moment, just a strong hunch.

Keith E. Peterson · May 2018

Use \cdot, which is a centered dot, instead of \mdot. Example: \[ x \cdot y. \]

or if you want a big round dot, use \bullet. Example: \[ x \bullet y. \]

Robert Figura · May 2018

Thanks, Keith, I figured that one out while you were typing. But I forgot how to create a standalone formula... No need to answer that one, I'll simply have a look at your comment's source as soon as I'm back in front of my laptop. Thanks again, to you, and in advance :^)

John Baez · May 2018

Robert wrote:

Which sequences of natural numbers arise by counting the number of paths of length n from the chosen node in a pointed graph to itself?

I'll consider a simpler graph: one that has distinct loops of lengths $a_1, ... a_k$. Then the number of paths with length $n$ that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients $b_i$ such that:
$$ n=\sum_i^k a_i \cdot b_i $$ I have no idea how to simplify that expression, but I claim it to be the answer to John's first question.

There are two issues here:

how you are reducing the case of a general graph to the simpler sort of graph you're discussing, and
how your formula works for those simpler graphs.

I'll focus on point 2. Could you illustrate how your formula works if I start with the "Fibonacci graph"?

It seems to be of your simpler sort, with a loop of length 1 and a loop of length 2.

John Baez · May 2018

Robert wrote:

It seems we should call these categories Fibonacci and Pell. Is that something people do?

No, not as far as I've ever heard. I like it, though.

Puzzle. There's another famous sequence, the Lucas numbers, also defined by a linear recurrence:

$$ L_0 = 2,\quad L_1 = 1,\quad L_{n+2} = L_{n+1} + L_n $$ Can we get this sequence as the number of loops of length $n$ starting and ending at some chosen node in a graph? If not, can we do it for a shifted version of this sequence? Or can we get it as the number of paths of length $n$ starting at some chosen node and ending at some other chosen node of a graph?

A study of 657 sunflowers show that most of them have Fibonacci numbers of spirals, while some have Lucas numbers.

Robert Figura · May 2018

Hey yes, my formula is wrong! Thanks! Let me translate your labeling of the Fibonacci graph to a loop signature.

$f \rightarrow a_1=1$

$h°g \rightarrow a_2=2$

I had proposed to count paths like this example with length 4:

$2\cdot a_1+1\cdot a_2$

While in fact these paths are all different:

$a_1a_1a_2$

$a_1a_2a_1$

$a_2a_1a_1$

I still like naming loops. The formula I gave simply isn't enough! For each such sum I'd also have to count the permutations which look different. Counting them shouldn't be too hard, but armed with such an ability there might be a better way to count them alltogether. Or even general paths with arbitrary start and end...

If it weren't a bit late for me, I might find out how to count these permutations right away, and then perhaps nevertheless try to correct my formula that way.

Christopher Upshaw · May 2018

So, going in a different direction, we get a weird directed two category if we index the morphisms of the free category by length.

(Not just an enriched category of some sort because id and composition only hold while moving to a later index)

Or you can look at the graph as a binary valued matrix then take powers of it as a matrix of natural numbers, then the sequences of particular diagonals are the sequences generated by the graph pointed at that node.

So would looking at traces and determinants help with building a pointed graph that generates a particular sequence?

John Baez · May 2018

Robert - good, you see the problem.

You might try counting the paths of various lengths in this graph:

and compare it to taking powers of this matrix:

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) .$$

Robert Figura · June 2018

Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D

Your suggestion indeed looks highly elegant: write down the adjacency matrix, take it to the n'th power, and then, as Christopher Upshaw said, simply read off... something... from the main diagonal. I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.

I'll have to take a closer look, especially to find out why that works! That is, once I get my hands free, which might well happen before the Americas wake up again.

Jonathan Castello · June 2018

Robert wrote:

I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.

The trace would give you the number of paths of length $n$ either of type $x \to x$ or of type $y \to y$. For instance, the square of that matrix gives:

$$ \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right) .$$ The trace of this matrix is 3, but we know there are only two paths of length 2 from x to itself. Do you see what's happening? (It has to do with the fact that the original matrix is, as you observed, the adjacency matrix for this graph.)

Also, notice that the adjacency matrix doesn't have to be binary-valued here. If we have two self-loops on a vertex, we'd need to put a 2 down for that vertex.

(I love the matrix approach to this problem! It's a wonderful example of one of Pólya's principles: sometimes, in order to prove a thing, you should prove a stronger thing instead.)

Pierre Prado · June 2018

Thanks @Matthew Dotty for the comment #22

Christopher Upshaw · June 2018

Yeah, I'm trying to remember what I know about raising a matrix to a power. Oh, the natural number powers of a matrix of natural numbers are again natural numbered matrices. So we can then reinterpret them as a graph. Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think!

Well the determinant of the product is the product of the determinants, so $1 \centerdot 0 - 1 \centerdot 1 = -1$ means that for the Fibonacci graph, the determinant of the power is going to alternate from negative one and one.

Jonathan Castello · June 2018

Christopher wrote:

Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think!

In some sense, a free category is the union over the sequence of all such graphs! (We don't even have to worry about pointed graphs in particular: powers of the adjacency matrix tell us about the number of paths between every pairs of vertices.)

MatthewDoty · June 2018

Christopher wrote

Yeah, I'm trying to remember what I know about raising a matrix to a power.

I made some Project Euler-esque puzzles after thinking about Puzzle 105 and Puzzle 104 in Fun With Recurrences

I'll try to post some answers to those tonight and show how do to matrix exponentiation in the process.

John Baez · June 2018

Robert wrote:

Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D

Who would have guessed! It's fine to make guesses here; I'm more interested in getting people thinking - and thinking out loud - than having people be infallible.

I believe your original formula was correct except that you need to count ordered sums of the loop lengths $a_i$, not ordinary sums. For example, the Fibonacci graph has loops of length 1 and 2 based at the point $x$:

and the number of loops of length $n$ based at this point is the number of ways of writing $n$ as an ordered sums of 1's and 2's. For example

$$ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 $$ so there are four loops of length 5... and the fourth Fibonacci number is 5.

Robert Figura · June 2018

John replied:

Who would have guessed!

Thanks! Guessing is fun, especially in groups! But shush now, or other people might think I'm worse than lazy.

Let's work a bit, as a distraction from work. Matrix multiplication works like this:

\[ c_{ij} = \sum_k^n a_{ik} \cdot b_{kj} \]

Let's say a is our adjacency matrix, and b the n-1th power of a. Every element $a_{ij}$ tells us wether there's an arrow $i \rightarrow j$. You can skip thinking recursively for now and just assume that $b=a$. Then $c_{ij}$ is the sum of all those $b_{kj}$ for which a states that there's an arrow $i \rightarrow k$. Nonrecursively, these are just the neighbours' arrows!

So these square matrices are just perfect for recording the inflow any element gets!

I still have to check how my initial formula relates to all this. Until then, maybe some of the folks reading here might enjoy this 5 page short distraction as much as I did:

"On the computation of the nth power of a matrix" by Nikolaos Halidias (2017): https://arxiv.org/abs/1705.04994

Keith E. Peterson · June 2018

Wait a minute...

If these arrows are weight by probabilities, then the above construction produces a Markov chain.

So the number of arrow or morphisms of a pointed graph is like a Markov chain with weight 1 for each arrow.

Robert Figura · June 2018

That's exactly right, Keith, if you can stomach the words "Markov chain"!

Christopher Upshaw · June 2018

Right, and if we want to be able to go backwards on a sequence, then we want to allow negative numbers of arrows. So the "graph" that will take us to the left on the Fibonacci sequence is \[ \left( \begin{array}{cc} 0 & 1 \\ 1 & -1 \end{array} \right) .\] I don't have a good interpretation of what that means as a path count, maybe just the standard difference between path counts? I don't think that works...

@KeithEPerterson a Markov chain is just a normalized path count. (Well if you have rational probabilities. :) )

John Baez · June 2018

Christopher:

Yeah, I'm trying to remember what I know about raising a matrix to a power. Oh, the natural number powers of a matrix of natural numbers are again natural numbered matrices. So we can then reinterpret them as a graph. Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think!

It becomes obvious if you take a small example, like the matrix

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) $$ coming from this graph

and square, cube, etc. the matrix while also counting paths of length 2, 3, etc. by hand. You'll see that the formula for matrix multiplication

$$ (AB)_{ij} =\sum_k A_{ik} B_{kj} $$ is exactly what you need for path counting, because the right-hand side says "to count the number of ways to go from node $j$ to node $i$, sum over all ways to go first from $j$ to some other node $k$ and then from $k$ to $i$".

There are few things so good for understanding math as actually multiplying matrices by hand. After working through this example for half an hour, it will seem so obvious that you'll realize this is exactly one of the things matrix multiplication was made for!

Heisenberg reinvented matrix multiplication when developing quantum mechanics, for more or less the same reason. Back then, in the 1920's, even good physicists didn't all know about matrices! So Heisenberg reinvented matrix multiplication. Then he told his thesis advisor, Max Born, who said something like "that's just matrix multiplication - read this book".

And thus matrix mechanics was born. Only much later did it become clear what was really going on: an interesting relation between quantum mechanics and category theory!

Fredrick Eisele · June 2018

To make the adjacency matrix notion painfully obvious.

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) $$ $$ \left( \begin{array}{c | cc} s \rightarrow t & x & y \\ \hline x & \lbrace f \rbrace & \lbrace g \rbrace \\ y & \lbrace h \rbrace & \emptyset \end{array} \right) $$

Azimuth Forum

Howdy, Stranger!

Categories

Lecture 36 - Categories from Graphs

Comments