Georgia Institute of Technology College of Sciences

The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives. First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_{mon} requires exponential time to converge. Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_{nn} in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x < y in order with bias 1/2 <= p_{xy} <= 1 and out of order with bias 1-p_{xy}. The Markov chain M_{mon} was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_{nn} and M_{mon} by using simple combinatorial bijections, and we prove that M_{nn} is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly, we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x < y, but for which the transposition chain will require exponential time to converge. Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete interfering binary mixtures by showing that they exhibit a "clustering property" at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.

The stability of a liquid drop of prescribed volume hanging from a circular cylindrical tube in a gravity field has been a problem of continuing interest. This problem was treated variationally in the late '70s by Henry Wente who showed there was a continuous family indexed by increasing volume which terminated in a final unstable equilibrium due to one or the other of two specific geometric mechanisms. I will describe a similar problem arising in mathematical biology for drops at the bottom of a rectangular tube and explain, among other things, how the associated instability occurs through exactly three physical mechanisms.

The viruses that infect bacteria have a hallowed position in the development of modern biology, and once inspired Max Delbruck refer to them as "the atom of biology". Recently, these viruses have become the subject of intensive physical investigation. Using single-molecule techniques, it is actually possible to watch these viruses in the act of packing and ejecting their DNA. This talk will begin with a general introduction to viruses and their life cycles and will then focus on simple physical arguments about the forces that attend viral DNA packaging and ejection, predictions about the ejection process and single-molecule measurements of ejection itself.

A linear cocycle over a diffeomorphism f of a manifold M is an automorphism of a vector bundle over M that projects to f. An important example is given by the differential Df or its restriction to an invariant sub-bundle. We consider a Holder continuous linear cocycle over a hyperbolic system and explore what conclusions can be made based on its properties at the periodic points of f. In particular, we obtain criteria for a cocycle to be isometric or conformal and discuss applications and further developments.