사각격자의 도미노 타일링 (dimer problem)

 

 

개요

• 사각격자를 도미노로 덮는 문제
• planar bipartite graph 의 perfect matching 문제로 생각할 수 있다
• 그래프의 적당한 weighted adjacency matrix 와 그 파피안(Pfaffian) 을 통해 답을 표현할 수 있다
• 통계물리에서는 dimer configuration = covering of a graph by pairs of fermions connected by an edge

 

 

2x2 격자

• 다음 두 가지 경우가 존재
  [/pages/10224838/attachments/5728746 dimer1.gif]
  
• 다음 행렬의 파피안(Pfaffian) 을 구해서 경우의 수를 얻을 수 있다
  \(\left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ -1 & 0 & 0 & -1 \\ -1 & 0 & 0 & 1 \\ 0 & 1 & -1 & 0 \end{array} \right)\)
  

 

 

\(\left( \begin{array}{cccc} 0 & t_{1,2} & t_{1,3} & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} \\ -t_{1,3} & 0 & 0 & t_{3,4} \\ 0 & t_{2,4} & -t_{3,4} & 0 \end{array} \right)\) 의 파피안은 \(t_{1,3} t_{2,4}+t_{1,2} t_{3,4}\) 으로 주어진다. 파피안의 각 항은 도미노 타일링에 대응된다. 

 

 

3x2 격자

• 다음 세 가지 경우가 존재
   [/pages/10224838/attachments/5728744 dimer2.gif]
  
• 다음 행렬의 파피안은 3이다
  \(\left( \begin{array}{cccccc} 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & -1 & 0 \end{array} \right)\)
  

 

\(\left( \begin{array}{cccccc} 0 & t_{1,2} & t_{1,3} & 0 & 0 & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} & 0 & 0 \\ -t_{1,3} & 0 & 0 & t_{3,4} & t_{3,5} & 0 \\ 0 & t_{2,4} & -t_{3,4} & 0 & 0 & -t_{4,6} \\ 0 & 0 & -t_{3,5} & 0 & 0 & t_{5,6} \\ 0 & 0 & 0 & t_{4,6} & -t_{5,6} & 0 \end{array} \right)\) 의 파피안은 \(t_{1,2} t_{3,5} t_{4,6}+t_{1,3} t_{2,4} t_{5,6}+t_{1,2} t_{3,4} t_{5,6}\) 이다.

 

역사

 

• http://www.google.com/search?hl=en&tbs=tl:1&q=
• 수학사연표

 

 

메모

• 8x8 격자에는 12988816 경우의 도미노 타일링이 있다
• http://www.science.uva.nl/onderwijs/thesis/centraal/files/f887198315.pdf
• http://www.math.oregonstate.edu/~math_reu/REU_Proceedings/Proceedings1991/Klarreich91.pdf
• Borcherds Lecture 26 Pfaffians and dominoes

• Math Overflow http://mathoverflow.net/search?q=

 

 

관련된 항목들

• 파피안(Pfaffian)

 

 

수학용어번역

• 단어사전
  
  • http://translate.google.com/#en%7Cko%7C
  • http://ko.wiktionary.org/wiki/
• 발음사전 http://www.forvo.com/search/
• 대한수학회 수학 학술 용어집
  
  • http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
• 한국통계학회 통계학 용어 온라인 대조표
• 남·북한수학용어비교
• 대한수학회 수학용어한글화 게시판

 

 

 

사전 형태의 자료

• http://ko.wikipedia.org/wiki/
• http://en.wikipedia.org/wiki/Domino_tiling
• The Online Encyclopaedia of Mathematics
• NIST Digital Library of Mathematical Functions
• The World of Mathematical Equations

 

 

 

 

 

관련논문

• http://www.jstor.org/action/doBasicSearch?Query=
• http://www.ams.org/mathscinet
• http://dx.doi.org/

 

 

관련도서

• 도서내검색
  
  • http://books.google.com/books?q=
  • http://book.daum.net/search/contentSearch.do?query=