DIMER MONOMER
Zac Hall
Dr. Bryan Shader
Planar monomer-dimer tilings
Monomer – 1 by 1 tile
Dimer – 2 by 1 tile or 1 by 2
Monomer-Dimer Tilings
Monomer-Dimer Tilings
What properties does a “random”
monomer-dimer tiling of a region have?
◦ Expected number of Dimers?
◦ Is a given cell more likely to be a monomer?
How can we generate a uniform, random
monomer-dimer tiling of a region?
Fundamental Questions:
Methods
◦ Computer-based simulations
Kastelyn’s Theorem
◦ Probabilistic Models (matrices)
◦ Analytical Models
Sage Math (Python) was used throughout
the year to aid us
Monomer-Dimer Tilings
N by N grids w/ 2 monomers, rest dimers
4 by 4
◦ 552 possible tilings
◦ Monomer’s probable locations: corners, sides,
center
1 6 2 2 6 1
6 by 6
◦ 363,536 possible tilings 6 5 4 4 5 6
◦ Probable Locations: 2 4 3 3 4 2
8 by 8
2 4 3 3 4 2
◦ 1,760,337,760 tilings
6 5 4 4 5 6
Beginning Work
1 6 2 2 6 1
Recursive Formulas:
2𝑁−2+1 1 𝑁−2
FN = 1 + 𝑁−1 EN + FN-3 + 𝑁−1(F0 + E2 8 2 N-2
) +
𝑁−4 𝑁−𝑘−2σ𝑘=1 𝑁−𝑘 (Fk + E2 N-k-2
)
E = σ𝑁−3
1 1
N 𝑘=0 2𝑘+1
(FN-k-2 + Ek) + 2𝑁−2
(F0 + EN-2)
EN = E(Dimers)
E20000 /20000 = 0.43344653343386
Bounded … Must Converge
1 by N : Mathematical Discoveries
Matrix A8:
◦ “Characteristic matrix” for monomer dimer tilings of
8 X 1 region
◦ A8^N represents “characteristic matrix” for
8 X N region
◦ Top-left entry represents the number of tilings
possible
◦ 8 X N plane: 256 X 256 matrix
◦ Created using numerical methods/coding
Enumerating 8 X N Tilings
Formula for total number of tilings
This is a 136th degree recursive formula:
TN =133* TN-1 +9461* TN-2 - 444475* TN-3
+… - 23797 TN-133 + 1027 TN-134 + 21 TN-15
- TN-136
lim TN/ TN-1≈170.8771576
N->∞
Recursive Formula for 8XN
Cayley-Hamilton theorem for a square
matrix
Satisfies a linear recurrence
Could do this for any kXN - first to do
8XN and find the recurrence for it
Counting problem with computational
difficulties for high N
Implications
Use the same “characteristic matrix” for
discerning vertical and horizontal dimers
Able to characterize our tilings with more
detail
Extension
Original 3X3 Updated 3X3
3 2 1 1 2 1 1 1 2𝑣 + 1 ℎ𝑣 + ℎ ℎ ℎ2 ℎ𝑣 + ℎ ℎ2 ℎ2 ℎ3
2 0 1 0 1 0 1 0 𝑣 + 1 0 ℎ 0 ℎ 0 ℎ2 0
1 1 0 0 1 1 0 0 1 ℎ 0 0 ℎ ℎ2 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
2 1 1 1 0 0 0 0 𝑣 + 1 ℎ ℎ ℎ2 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0 1 ℎ 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
Extension
Found a relationship for AN :
𝑣 ∗ 𝐴𝑘−2 0 0 0
𝐴 ℎ ∗ 𝐴 0 0 0 0
𝐴𝑘 =
𝑘−1 𝑘−1 +
𝐴𝑘−1 0 0 0 0 0
0 0 0 0
Can extend this to our simple numerical
example
Create more characteristic equations for k
X N regions
Extension
Static -> Dynamic
Explored various regions: N by N, 2 by N,
1 by N
Began as all monomers, “paired” to
become dimers.
Pair until “frozen”
Generating tilings
Creating probability distributions for any
MXN area (E(dimers))
◦ Created every possible tiling by coding it
Represented by matrix of 0’s, 1’s, 2’s
◦ Use these tilings to create probability
distibutions
Computational issues:
◦ 6 X 6 possibilities aren’t able to be calculated
in less than 2 hours
◦ Probabilities require ‘permanent’ calculation –
even more difficult
Final work
Finding tiling distribution – need to find
probabilities for ending with each
Finding a formula for E(dimers) as a
recursion? Possibly the same recurrence
with different initial conditions?
Applications in diatomic nuclear bonding
and ice-formations
Future Potential Research
Thank you.