ドミノ()は、2つの同一の正方形を辺で連結したポリオミノ(2-ポリオミノ)である。回転および鏡映による一致を同一視する(自由ポリオミノ)とドミノは1種類であり、回転・鏡映を区別して数える(固定ポリオミノ)と横向きと縦向きの2種類になる。

数学では、格子状領域をドミノで隙間なく埋めるドミノタイリングが重要な対象であり、グラフ理論(完全マッチング)や統計力学(dimer model)と深く関係する。

歴史 ポリオミノはドミノの一般化として位置づけられ、名称「polyomino」はソロモン・ゴロムによって普及した。

定義と同値関係 ポリオミノの数え上げでは、図形の同一視の規則(回転・鏡映の扱い)により種類数が変わる。一般に、回転・鏡映を同一視するものを自由ポリオミノ、鏡映のみを区別するものを片面(one-sided)ポリオミノ、回転・鏡映をともに区別するものを固定ポリオミノと呼ぶ。 ドミノは2-ポリオミノの基本例で、自由および片面としては1種類、固定としては2種類である。

ドミノタイリング 黒白彩色(市松模様)による必要条件 格子を市松模様に2色で塗り分けると、ドミノは必ず異なる2色のマスを1つずつ覆う。したがって、領域がドミノでタイリング可能であるためには、黒マスと白マスの個数が等しいことが必要条件となる。 この種の不変量は、ドミノタイリングの不可能性を示す基本的手法として広く用いられる。

完全マッチングとの対応 有限の格子領域のドミノタイリングは、その領域の双対グラフ(格子正方形を頂点とし、辺共有で隣接とするグラフ)の完全マッチングに1対1に対応する。 この対応により、ドミノタイリング問題はグラフ理論と線形代数の道具(行列式・Pfaffian等)で解析できる。

古典結果と解析手法 矩形領域の数え上げ(Kasteleyn/Temperley–Fisher/Fisher) 正方格子上の長方形領域のドミノタイリングの個数は、1961年にP. W. Kasteleyn、およびH. N. V. TemperleyとM. E. Fisherらにより厳密に数え上げ可能であることが示された。 これらの結果はKasteleynの方法(Pfaffian/行列式による計数)として整理され、その後の解説でも導入的に扱われる。

dimer model(双体模型)との関係 ドミノタイリングは、格子上のdimer model(辺に対応するダイマーが頂点を被覆する模型)としても解釈され、統計力学・確率論の文脈で研究される。

確率論・極限形状 一様ランダムなドミノタイリングを考えると、典型的なタイリングの大域的形状が境界条件により記述できることがある。Cohn–Kenyon–Proppは、ランダムドミノタイリングに関する変分原理(エントロピー積分の最大化)を与え、極限形状(limit shape)現象を体系的に扱った。

また、Aztec diamond と呼ばれる領域の一様ランダムドミノタイリングでは「arctic circle theorem」として知られる凍結領域の出現が示されている。 Kenyonは、高さ関数のゆらぎのスケーリング極限がガウス自由場(Gaussian free field)に収束することを示し、確率論的側面を発展させた。

計算量と一般化 平面領域のドミノタイリングは完全マッチングに帰着できるため、決定問題・計数問題ともに多項式時間で扱える枠組みが存在する。 一方で、ドミノの一般化(高次元でのタイリング、別種のタイル集合など)では、NP完全や#P完全といった計算困難性が現れることが示されている。

関連項目 ポリオミノ ドミノタイリング タイル張り 完全マッチング ワンのタイル

脚注