|
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).
|
|
|
|