Page 317 -

304 Exercises

Table 6.2. Use it to compute the analogous his- approximately equal frequency (see Table 6.2).
tograms on the 6 × 6 lattice with or without peri- NB: An analogous algorithm exists for the two-
odic boundary conditions, but make sure that your dimensional Ising model, and the Ising spin glass.
representation allows you to treat sufficiently large In that latter case, unlike for dimers, there are no
numbers without overflow. Store all the complete good Markov-chain sampling methods.
dimer configurations in a file and compute the pair (6.11) The matrices {A 1,...,A 4} in Fig. 6.39 allow one to
correlation functions of Table 6.6. count complete dimer configurations with periodic
(6.9) Generalize Alg. 6.6 (breadth-dimer) for tetris boundary conditions: consider an arbitrary alter-
molecules (see Fig. 6.38) on an L×L square lattice nating cycle, either planar or winding around the
without periodic boundary conditions. Start from lattice (in x or y direction, or both). Compute its
a list of single-tetris configurations analogous to weight for all four matrices (see Kasteleyn (1961)).
Fig. 6.18. How many configurations of eight tetris Show that the number of complete dimer configura-
molecules are there on a 7 × 7 lattice? tions on the square lattice with periodic boundary
conditions is
1
Z = (−Pf A 1 +Pf A 2 +Pf A 3 +Pf A 4).
2
Implement matrices analogous to {A 1,..., A 4} for
L × L square lattices with periodic boundary con-
ditions, and recover the results for complete dimer
configurations in Tables 6.2 and 6.3.
{x,y}

+ − + − − + − + + − + − − + − +
Fig. 6.38 Tetris molecules onan8 × 8 lattice. +++ − +++ − +++ + +++ +
− + − + − + − + − + − + − + − +
+++ − +++ − +++ + +++ +
− + − + − + − + − + − + − + − +
+++ − +++ − +++ + +++ +
NB: The enumeration program relies on a list of − + − + − + − + − + − + − + − +
+++ − +++ − +++ + +++ +
single-molecule configurations, and on a list of sites
touched by each of them (there are 24 such config- A 1 A 2 A 3 A 4
urations on the 4×4 lattice, and 120 configurations
on the 6 × 6 lattice). Write down explicitly that a Fig. 6.39 Standard matrices for the 4 × 4 lattice (com-
pare with Fig. 6.25).
molecule based at {x, y} (where 1 ≤ x, y ≤ L),
in the same orientation as the dark molecule in
Fig. 6.38, exists if x +3 ≤ L and if y +1 ≤ L and (6.12) Implement the pivot cluster algorithm for dimers
then touches also the positions {x +1,y}{x +2,y} on the L × L square lattice with periodic bound-
{x+3,y},and {x+1,y +1}. All coordinates {x, y} ary conditions. Test it by writing out complete
should then be translated into site numbers. dimer configurations on file: on the 4×4 lattice, the
(6.10) Implement the matrix A of eqn (6.18), general- 272 complete dimer configurations should be gen-
ized for an L × L square lattice without periodic erated equally often. Sample configurations with
2
boundary conditions (see Fig. 6.25). Use a stan- M< L /2 dimers and store them on file. Now show
dard linear algebra routine to compute det A and how a single iteration of Alg. 6.6 (breadth-dimer)
√
Pf A = det A. Test your implementation against allows one to estimate N(M +1)/N(M). Estimate
the enumeration results of Table 6.2 and Table 6.3. N(M) from several independent Monte Carlo runs.
Extend the program to compute Pfaffians of mod- Test your procedure in the 4 × 4 lattice and the

ified matrices, as A and A in Fig. 6.27. Then im- 6 × 6 lattices against enumeration data, try it out
plement a Pfaffian-based rejection-free direct sam- on much larger lattices.
pling algorithm for complete dimer configurations. NB: Thus it is easy to estimate the number of
At each step during the construction of the config- dimer configurations for any M,because Markov-
uration, the algorithm picks a site that is not yet chain Monte Carlo algorithms converge very well.
covered by a dimer, and must compute probabil- We note that Valiant (1979) has rigorously estab-
ities for the different orientations of the dimer on lished that counting the number of monomer–dimer
that site, as discussed in Fig. 6.28. Check your algo- configurations without statistical errors is difficult:
rithm in the 4×4 square lattice. It should generate estimation is easy, precise counting difficult.
the 36 different complete dimer configurations with