M Theory Lesson 245

The $3\times 3$ code circulant $C=(0,1,1)=\left(231\right)+\left(312\right)$ appears in a standard generating method for a three dimensional representation of the braid group $B_3$, which we may discuss later. For now, observe that powers of $C$ define circulants $C^n=(x,y,y)$ where the sequences of $x$ and $y$ are given by

$x_n\in 0,2,6,10,22,42,\cdots$
$y_n\in 1,3,5,11,21,43,\cdots$

After the initial terms, $y_n$ settles down to $y_n=y_{n-1}+x_{n-1}$, which is always equal to $x_n\pm 1$. The sequence $x_n$ is number A078008 in the database. That is, $3x_n\equiv A_n$ gives the chromatic polynomial for 3 colours of the cyclic polygon graph on $n$ sides. In terms of the Tutte polynomial $T\left(t\right)$, $A_n\left(t\right)$ may be expressed as

$A_n\left(t\right)=(-1{)}^{n-1}tT(1-t,0)$

Similarly, for the $4\times 4$ case $C=(0,1,1,1)$, the sequence $x_n$ is given by A054878. This sequence is associated with paths on a square, whereas the $3\times 3$ sequence is associated with paths on a triangle. Note that $C$ is the adjacency matrix for the triangle.

In general, calculating the chromatic polynomial of a graph is an NP-complete problem. By splitting the circulant matrix elements into 2 sequences, it is easy to define $x_n$ in terms of the simple recursion $x_n=y_n+(-1{)}^{n-1}$, where $y_n$ itself is built from the Fibonacci type rule above.