M Theory Lesson 245
The $3 \times 3$ code circulant $C = (0,1,1) = (231) + (312)$ 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, $3 x_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(t)$, $A_n (t)$ may be expressed as
$A_{n} (t) = (-1)^{n-1} t T(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.
$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, $3 x_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(t)$, $A_n (t)$ may be expressed as
$A_{n} (t) = (-1)^{n-1} t T(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.
posted by Kea | 1:14 PM
0 Comments:
Post a Comment
<< Home