Seungsang Oh, Enumeration of multiple self-avoiding polygons in a confined square lattice

Enumeration of multiple self-avoiding polygons in a confined square lattice

2014/10/07 *Tuesday 5PM-6PM*
Room 1409

$\mathbb{Z}_{m \times n}$ is the rectangle of size $m \times n$ in the square lattice. $p_{m \times n}$ denotes the cardinality of multiple self-avoiding polygons in $\mathbb{Z}_{m \times n}$ .

In this talk, we construct an algorithm producing the precise value of $p_{m \times n}$ for positive integers m,n that uses recurrence relations of state matrices which turn out to be remarkably efficient to count such polygons. $$ p_{m \times n} = \mbox{(1,1)-entry of the matrix } (X_m)^n -1$$ where the matrix $X_m$ is defined by $$ X_{k+1} = \left( \begin{array}{cc} X_k & O_k \\ O_k & X_k \end{array}\right) \ \ \mbox{and} \ \ \ O_{k+1} = \left( \begin{array}{cc} O_k & X_k \\ X_k & 0 \end{array} \right) $$ for $k=1, \cdots, m-1$ , with $1 \times 1$ matrices $X_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$ and $O_1 = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$ .

Tags: 오승상

This entry was posted on Tuesday, September 23rd, 2014 at 11:01 am and is filed under 2014, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.