#Creator: drawtiling.c #Vax file #Title: Fortress of order 4 8 16 AAVVAA AVVAAVVA AAVVAAVVAAVVAA AVVAAVVAAVVAAVVA VAAVVAAVVAAVVAAV VVAAVVAAVVAAVV VAAVVAAV VVAAVVAll of the # lines are comments, ignored by vaxrandom but useful for reference. The first line under the comments contains the maximum number of rows and columns to allocate for the region. If these numbers are too small, vaxrandom will not allocate enough space for the matching and will return an error. If the numbers are larger than the number of rows and columns, it is fine with vaxrandom; vaxrandom will allocate more space than needed.

The VAX characters behave in the standard way. X matches all four directions, A all directions except up, V all directions except down, < all directions except left, and > all directions except right.

Vaxrandom uses the standard Propp-Wilson algorithm by first making a perfect matching using a breadth first search and a max-flow algorithm. It reports right away if the region does not permit a perfect matching. It then computes the maximum and minimum matchings of the region and finally it raises and lowers cycles in the matchings so that the two matchings coalesce. The algorithm starts with an initial number of timesteps (remembering the random coin flips it used), and if the lower and upper matchings didn't coalesce, it goes back twice as far into the past and tries again. It continues until it succeeds.

-vax | outputs a random perfect matching in ASCII form using brackets and AV to denote edges. This is the default. |

-ps | outputs a random perfect matching as a postscript file. |

-height | outputs a height function of a random perfect matching where the height of each vertex is the number of times a cycle with that vertex has been raised. The height at a vertex is -1 if the vertex is outside the region. This option is not used much anymore. |

-seed [value] | uses the specified value as the initial random seed. This allows for the reproducibility of experiments. One bit of caution though is the seed depends on what platform you are using. |

-initial [value] | starts the Propp-Wilson algorithm using [value] timesteps back in to the past. The default is 128. |

-minonly | doesn't compute a random matching; only outputs the minimum matching |

-maxonly | doesn't compute a random matching; only outputs the maximum matching |

-showcycles | doesn't compute a random matching; only outputs the index of each cycle of the graph. Used for debugging. |

-report | print a progress report of the
Propp-Wilson algorithm giving output like
Starting at time -128, at time -32, max is 76, min is 22, difference is 54.which shows the initial value of t, the current value of t, and the volume under the upper and lower height functions and their difference. The upper and lower matchings have coupled when their volumes are equal and the difference is 0. By looking at the report, we can see if the Propp-Wilson algorithm is close to finishing or if there is a long way to go. This is useful when computing random perfect matchings of large regions that are expected to take a long time. |

-time | Gives the time that the Propp-Wilson reached certain points in the computation. This is also useful for large regions that are expected to take a long time. |

-bound [value] | starts with the upper matching,
randomly flips cycles for value time steps (not using Propp-Wilson)
and outputs the final state of the matching. Note this does
not yield a random perfect matching. |

-version | outputs the current working version of vaxrandom. |

-help | outputs a brief help message on how to use vaxrandom. |

athena% drawtiling -fortress 4 > fort4 athena% vaxrandom fort4 Matching 88 vertices end mark V ...................................................................... This is vaxrandom version 3.01. The initial seed was -1954326176. Random matching generated after 128 time steps. #Matching #Creator: vaxrandom.c #Platform: sun4 #Title: Fortress of order 4 #Seed: -1954326176 #Random matching made in 128 timesteps 8 16 <><><> A<>A<><> A<>V<>V<>A<>AA AV<>A<>A<>V<>VVA VA<>VAAV<><><>AV V<>AVVAA<>A<>V V<>VVAAV <><>VVThis output is a random matching of the fortess shown earlier.

If you have any questions or comments, send an email to mdblum@mit.edu .