오승상 Archives - KAIST Discrete Math Seminar KAIST Discrete Math Seminar

Posts Tagged ‘오승상’

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

Tuesday, September 23rd, 2014

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)$ .