
Discrete Mathematics and Optimization Seminar

Oct. 20, 2008
Branched Polymers
Peter Winkler
Dartmouth

A branched polymer is a finite, connected set
of nonoverlapping 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 3space. Our
methods also permit computation of expected diameter in
3space, and provide a simple combinatorial proof for a
notoriously hard theorem concerning random walks.
Joint work with Rick Kenyon (Brown).



