In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

Height functions
For some classes of tilings on a regular grid in two dimensions, it is possible to define a height function associating an integer to the vertices of the grid. For instance, draw a chessboard, fix a node  with height 0, then for any node there is a path from  to it. On this path define the height of each node  (i.e. corners of the squares) to be the height of the previous node  plus one if the square on the right of the path from  to  is black, and minus one otherwise.

More details can be found in .

Thurston's height condition
 describes a test for determining whether a simply-connected region, formed as the union of unit squares in the plane, has a domino tiling. He forms an undirected graph that has as its vertices the points (x,y,z) in the three-dimensional integer lattice, where each such point is connected to four neighbors: if x + y is even, then (x,y,z) is connected to (x + 1,y,z + 1), (x − 1,y,z + 1), (x,y + 1,z − 1), and (x,y − 1,z − 1), while if x + y is odd, then (x,y,z) is connected to (x + 1,y,z − 1), (x − 1,y,z − 1), (x,y + 1,z + 1), and (x,y − 1,z + 1). The boundary of the region, viewed as a sequence of integer points in the (x,y) plane, lifts uniquely (once a starting height is chosen) to a path in this three-dimensional graph. A necessary condition for this region to be tileable is that this path must close up to form a simple closed curve in three dimensions, however, this condition is not sufficient. Using more careful analysis of the boundary path, Thurston gave a criterion for tileability of a region that was sufficient as well as necessary.

Counting tilings of regions

The number of ways to cover an  rectangle with  dominoes, calculated independently by  and , is given by
 

When both m and n are odd, the formula correctly reduces to zero possible domino tilings.

A special case occurs when tiling the  rectangle with n dominoes: the sequence reduces to the Fibonacci sequence.

Another special case happens for squares with m = n = 0, 2, 4, 6, 8, 10, 12, ... is

These numbers can be found by writing them as the Pfaffian of an  skew-symmetric matrix whose eigenvalues can be found explicitly. This technique may be applied in many mathematics-related subjects, for example, in the classical, 2-dimensional computation of the dimer-dimer correlator function in statistical mechanics.

The number of tilings of a region is very sensitive to boundary conditions, and can change dramatically with apparently insignificant changes in the shape of the region. This is illustrated by the number of tilings of an Aztec diamond of order n, where the number of tilings is 2(n + 1)n/2. If this is replaced by the "augmented Aztec diamond" of order n with 3 long rows in the middle rather than 2, the number of tilings drops to the much smaller number D(n,n), a Delannoy number, which has only exponential rather than super-exponential growth in n. For the "reduced Aztec diamond" of order n with only one long middle row, there is only one tiling.

Tatami
Tatami are Japanese floor mats in the shape of a domino (1x2 rectangle). They are used to tile rooms, but with additional rules about how they may be placed. In particular, typically, junctions where three tatami meet are considered auspicious, while junctions where four meet are inauspicious, so a proper tatami tiling is one where only three tatami meet at any corner. The problem of tiling an irregular room by tatami that meet three to a corner is NP-complete.

Applications in statistical physics 
There is a one-to-one correspondence between a periodic domino tiling and a ground state configuration of the fully-frustrated Ising model on a two-dimensional periodic lattice. To see that, we note that at the ground state, each plaquette of the spin model must contain exactly one frustrated interaction. Therefore, viewing from the dual lattice, each frustrated edge must be "covered" by a 1x2 rectangle, such that the rectangles span the entire lattice and do not overlap, or a domino tiling of the dual lattice.

See also
Gaussian free field, the scaling limit of the height function in the generic situation (e.g., inside the inscribed disk of a large aztec diamond)
Mutilated chessboard problem, a puzzle concerning domino tiling of a 62-square area of a standard 8×8 chessboard (or checkerboard)
Statistical mechanics

Notes

References

Further reading

Combinatorics
Exactly solvable models
Lattice models
Matching (graph theory)
Statistical mechanics
Tiling puzzles
통계역학과 그래프 이론에서 이합체 모형(二合體模型, )은 어떤 그래프 위의 완벽 부합들의 공간 위에 정의되는 통계역학 모형이다.

정의

이합체 모형 
다음과 같은 데이터가 주어졌다고 하자.
 유한 그래프 
 실수 값 함수 . 이를 각 변의 에너지라고 한다.
그렇다면, 의 완벽 부합들의 집합을

로 표기하자. 통계 역학에서, 완벽 부합은 보통 이합체 배치(二合體配置, )라고 하며, 그래프의 변은 이합체라고 한다. 즉, 흔히 사용되는 수학 용어 및 대응되는 물리학 용어는 다음과 같다.

이제, 다음과 같은 통계 역학 모형을 정의할 수 있다.
 위상 공간은 완벽 부합의 집합 이다.
 임의의 완벽 부합 의 에너지는 부합에 속하는 변들의 에너지들의 합 이다.
 온도 에서, 위상 공간 위의 측도는 이 에너지 함수 로 정의되는 기브스 측도이다.
 
 
여기서 값 는 분배 함수이다. 이 통계 역학 모형을 이합체 모형이라고 한다.

단량체-이합체 모형 
다음과 같은 데이터가 주어졌다고 하자.
 유한 그래프 
 실수 값 함수 . 이를 이합체 에너지(二合體energy, )라고 한다.
 실수 값 함수 . 이를 단량체 에너지(單量體energy, )라고 한다.
그렇다면, 의 부합들의 집합을

로 표기하자.

이제, 다음과 같은 통계 역학 모형을 정의할 수 있다.
 위상 공간은 부합의 집합 이다.
 임의의 부합 의 에너지는 부합에 속하는 변들의 이합체 에너지들과, 부합에 인접하지 않는 꼭짓점들의 단량체 에너지들의 합이다.
 
 온도 에서, 위상 공간 위의 측도는 이 에너지 함수 로 정의되는 기브스 측도이다.
 
 
여기서 값 는 분배 함수이다. 이 통계 역학 모형을 단량체-이합체 모형()이라고 한다.

성질

단량체-이합체 모형과 이합체 모형의 관계 
적어도 하나 이상의 완벽 부합을 갖는 유한 그래프 위에서, 만약 단량체 에너지를 무한대로 취할 경우,

단량체-이합체 모형은 이합체 모형으로 수렴한다.

상관 함수 
유한 그래프  위의 이합체 모형이 주어졌다고 하자. 각 변 에 대하여, 관측 가능량 을 지시 함수

로 정의할 수 있다. 이에 따라, 임의의 변 집합

에 대하여, 상관 함수

를 정의할 수 있다. 만약 가 서로 닿는 두 변을 포함한다면,

이다.

보다 일반적으로, 유한 그래프  위의 단량체-이합체 모형이 주어졌다고 하자. 그렇다면, 각 변  및 각 꼭짓점 에 대하여 지시 함수 관측 가능량

을 정의할 수 있다. 이에 따라, 임의의 변 집합

및 꼭짓점 집합

에 대하여, 상관 함수

를 정의할 수 있다. 만약 가 서로 닿는 두 변을 포함하거나, 만약 의 원소가 의 원소와 인접한다면,

이다.

예 

2차원 이징 모형은 피셔 격자()라는 어떤 특별한 평면 삼차 그래프 위의 이합체 모형과 동치이다. 피셔 격자는 정12각형과 정삼각형으로 구성된 평면 테셀레이션의 그래프이다.

구체적으로, 평면의 정사각 격자 그래프에서, 각 꼭짓점
╳
을 나비 모양의 삼차 그래프
─┬┐ ┌┬─
 │├─┤│
─┴┘ └┴─
로 치환하여 얻는다. 즉, (45도 회전하여 그린) 사각형 격자의 부분
 ╳
╳ ╳
 ╳
은 피셔 격자의 부분
      ─┬┐ ┌┬─
       │├─┤│
─┬┐ ┌┬─┴┘ └┴─┬┐ ┌┬─
 │├─┤│       │├─┤│
─┴┘ └┴─┬┐ ┌┬─┴┘ └┴─
       │├─┤│
      ─┴┘ └┴─
에 대응한다.
이 경우, 각 꼭짓점에서 완벽 부합은 다음과 같은 8개의 가능한 꼴을 가진다.

(굵게 표현된 변이 완벽 부합에 속하는 변이다.)

즉, 이는 2차원 이징 모형의 임의의 상태에서, 각 스핀 사이의 변을
 서로 다른 스핀 사이의 변은 굵게,
 서로 같은 스핀 사이의 변은 가늘게
칠한 뒤, 각 꼭짓점을 위와 같은 8개의 나비 그래프 가운데 하나로 치환하면, 이징 모형의 각 상태와 피셔 격자의 완벽 부합 사이의 2대 1 대응을 얻는다. (2대 1인 것은 이징 모형의 상태에서 모든 스핀을 뒤집어도 같은 완벽 부합에 대응하기 때문이다.)

예를 들어, (45도 기울여서 그린) 평면 이징 모형의 상태의 일부분이
    ╲ ╱
     +
  ╲ ╱ ╲ ╱
   +   +
╲ ╱ ╲ ╱ ╲ ╱
 −   +   +
╱ ╲ ╱ ╲ ╱ ╲
   +   −
  ╱ ╲ ╱ ╲
     −
    ╱ ╲
와 같은 꼴이라면, 이는 다음과 같은 피셔 격자 완벽 부합에 대응한다.
      ─┰┐ ┌┰─
       ┃┝━┥┃ 
━┭┐ ┌┰─┸┘ └┸─┮┓ ┏┭─
 │┝━┥┃       │┞─┦│
━┵┘ └┸─┮┓ ┌┮━┵┘ └┶━
       │┞─┧│ 
      ━┵┘ ┗┵─

참고 문헌

독서 자료

외부 링크 
 

통계역학
그래프 이론
격자 모형