ドミノタイリング

ユークリッド平面上のある領域のドミノタイリング(domino tiling)とは、右の図のようにドミノで領域を埋め尽すことである。同じことであるが、ドミノタイリングは、各々のドミノの中心に頂点として隣合うドミノの 2つの頂点を結ぶことで形成される(grid graph)のマッチングのことでもある。モノマー、ダイマー、ポリマーと呼ぶように、2つの原子が繋がったという意味であるユークリッド平面上の（あるいは、トーラス formula_1 上の）ダイマーモデル（Dimer model，双体模型）は、(polygon division)をもたらすモデルであり、完全マッチングであるダイマーモデルは、ドミノタイリングと同義である。
高さ函数.
2次元の正方形の格子上のタイリングのクラスに対し、格子のノードへ整数を割り当てる高さ函数を定義することができる。例えば、チェスボード（格子を黒と白の市松模様とする）を描いて、高さ 0 を持つノード formula_2 を固定すると、どのノードに対しても formula_2 からの経路が存在する。この経路上で、各々のノード formula_4 (つまり、四方形の頂点）の高さを、formula_5 から formula_4 への経路の右側の四方形が黒であれば、前のノード formula_5 に 1 をプラスした値とする。そうでなければ、1 をマイナスした値とする。
さらに詳しくは、に記載がある。
サーストンの高さ条件.
ウィリアム・サーストン(William Thurston)は、1990年に平面内の単連結な領域が、単位四方形の組（ドミノ）によりドミノタイリングとして形成されるか否かを決定できることを著した。彼は、3次元の(integer lattice)の中の点 ("x","y","z") を頂点として持つような無向グラフを作った。そこでは各々の点が 4つの近傍に連結していて、"x"+"y" が偶数であれば、("x","y","z") は ("x"+1,"y","z"+1), ("x"-1,"y","z"+1), ("x","y"+1,"z"-1), ("x","y"-1,"z"-1) と連結し、一方、"x"+"y" が奇数であれば、("x","y","z") は ("x"+1,"y","z"-1), ("x"-1,"y","z"-1), ("x","y"+1,"z"+1), ("x","y"-1,"z"+1) と連結している。この領域の境界は、("x","y") 平面の中の整数の点の列として見なすと、この一意に (three-dimensional graph)の中の経路へ（一度、初期の高さを決めると）持ち上げることができる。この領域がタイリング可能であるための必要条件は、この経路が 3次元で単純な閉曲線を形成することを除いて閉じている必要がある。しかし、この条件だけでは充分でない。境界の経路のより注意深く解析して、サーストンは必要かつ充分な領域のタイリングの可能性の判定条件を与えた。
領域のタイリングの数.
formula_8 の長方形を formula_9 個のドミノで埋め尽くす方法が何通りあるかの個数の公式は、独立に、 と により計算され、
として得られた。
この特別な場合として、formula_11-長方形のタイリングの方法が何通りあるかという問題がある。この数は、フィボナッチ数列の "n"-番目の数である 。
他の特別な場合として、"m" = "n" = 0, 2, 4, 6, 8, 10, 12, ... であるようなケースがある。
これらの何通りあるかという数は、固有値が明確に分かる formula_12 個の交代行列のパフィアンとして記述することにより、計算することが可能となる。このテクニックは多くの数学的に関連する問題へ適用することが可能である。例えば、統計力学での(dimer-dimer correlator function)の古典的 2次元の計算がある。
領域のタイリングの数は境界条件に対して非常に敏感で、一見たいしたことのない形の変化であっても、その数が劇的に変化する場合がある。わかりやすい例に、位数 "n" の(Aztec diamond) があり、このタイリングの数は、2("n" + 1)"n"/2 である。一方、位数が同じ "n" でも、中央の長い列が2列ではなく3列に 拡張されたアステカダイアモンド になると、タイリングの数は"n" のテトレーションから大きく減少し、指数的な数である(Delannoy number) D("n","n") に等しくなる。また、中央列が1列である 縮小されたアステカダイアモンドは、たったひとつのタイリングしか持たない。