Georgia Institute of Technology College of Sciences

Many statistical physics models are defined on an infinite lattice by taking appropriate limits of the model on finite lattice regions. A key consideration is which boundary to use when taking these limits, since the boundary can have significant influence on properties of the limit. Fixed boundary conditions assume that the boundary cells are given a fixed assignment, and free boundary conditions allow these cells to vary, taking the union of all possible fixed boundaries. It is known that these two boundary conditions can cause significant differences in physical properties, such as whether there is a phase transition, as well as computational properties, including whether local Markov chain algorithms used to sample and approximately count are efficient. We consider configurations with free or partially free boundary conditions and show that by randomly extending the boundary by a few layers, choosing among only a constant number of allowable extensions, we can generalize the arguments used in the fixed boundary setting to infer bounds on the mixing time for free boundaries. We demonstrate this principled approach using randomized extensions for 3-colorings of regions of Z2 and lozenge tilings of regions of the triangle lattice, building on arguments for the fixed boundary cases due to Luby et.al. Our approach yields an efficient algorithm for sampling free boundary 3-colorings of regions with one reflex corner, the first result to efficiently sample free boundary 3-colorings of any nonconvex region. We also consider self-reducibility of free boundary 3-colorings of rectangles, and show our algorithm can be used to approximately count the number of free-boundary 3-colorings of a rectangle.