Dimers.jl

A Julia package for sampling the dimer model on a grid
Popularity
1 Star
Updated Last
10 Months Ago
Started In
March 2015

Dimers

Dimers is a package for simulating the dimer model on a 2D rectangular grid, using an algorithm of Kenyon, Propp, and Wilson. Dimers also provides support for loop erased random walks and Wilson's algorithm on an arbitrary graph.

showgraphics(drawgraph(dimersample(20)))

Dimer sample

We can also compute the height function associated with the dimer sample:

dimerheight(dimersample(20))
11x11 Array{Int64,2}:
  0   1   0   1   0  1   0   1   0   1   0
 -1  -2  -1  -2  -1  2  -1  -2  -1  -2  -1
  0  -3  -4  -3   0  1   0   1   0  -3   0
 -1  -2  -1  -2  -1  2  -1  -2  -1  -2  -1
  0  -3   0   1   0  1   0   1   0   1   0
 -1  -2  -1   2  -1  2  -1  -2  -1   2  -1
  0   1   0   1   0  1   0   1   0   1   0
 -1  -2  -1   2  -1  2   3   2  -1  -2  -1
  0   1   0   1   0  1   0   1   0   1   0
 -1   2   3   2   3  2   3   2   3   2  -1
  0   1   0   1   0  1   0   1   0   1   0

Wilson takes a graph as its first argument and an array of true/false values specifying the roots.

showgraphics(drawgraph(Wilson(G,[[true];[false for i=1:length(G.vertices)-1]])))

UST sample

LERW(G,v0,roots) samples a loop-erased random walk on the graph G starting from the vertex whose index in G.vertices is v0 stopped upon hitting one of the vertices v for which roots[v] is true.

import Graphs
n = 100
G = Graphs.adjlist((Int64,Int64),is_directed=false)

for i=1:n
    for j=1:n
        Graphs.add_vertex!(G,(i,j))
    end
end

roots = Bool[v[1] == 1 || v[1] == n || v[2] == 1 || v[2] == n  for v in
G.vertices];

v0 = find(x->x==(div(n,2),div(n,2)),G.vertices)[1]

lerw = LERW(gridgraph(n),v0,roots)
for i=1:length(lerw)-1
    add_edge!(G,lerw[i],lerw[i+1])
end

showgraphics(drawgraph(G))

Loop-erased random walk sample

Build Status