Discrete Mathematics and Optimization Seminar
Oct. 20, 2008
Branched Polymers
Peter Winkler
Dartmouth
A branched polymer is a finite, connected set of non-overlapping unit balls in space. On account of their use as a physical model in chemistry and biology, it is desirable to generate random branched polymers so that behavior comparisons can be made. Previous attempts have used grid models and rejection sampling, but these have severly limited efficiency. However, by rederiving recent work of Bridges and Imbrie using elementary methods, we can generate perfectly random branched polymers in the plane and 3-space. Our methods also permit computation of expected diameter in 3-space, and provide a simple combinatorial proof for a notoriously hard theorem concerning random walks. Joint work with Rick Kenyon (Brown).