Combinatorial Methods for Random Structures in the Plane

Dartmouth College, Hanover NH

Investigators

Abstract

ABSTRACT Principal Investigator: Winkler, Peter Proposal Number: DMS - 0901475 Institution: Dartmouth College Title: Combinatorial Methods for Random Structures in the Plane The PI will tackle three random models in the plane, all of which show signs of benefiting from the application of combinatorial techniques. The first of these concerns branched polymers; the second, hard-core gases; the third, coordinate percolation. Branched polymers are connected configurations of spheres in space; their partition functions can be computed combinatorially in dimensions 2 and 3. Hard-core gases are random sets of non-overlapping spheres in space; here the PI has some ideas for discrete versions which may help in proving the existence of a solid-state phase. Finally, combinatorial techniques applied to coordinate percolation, in which the life of a site depends on events associated with the lines that cross there, has already yielded an exact expression for percolation probability. The three models are connected to applications in biochemistry, physics and computer science. Complex tree-like forms of proteins, hemoglobins, and molecules involved in photosynthesis can be compared with random mathematical ``branched polymers'' to help discern the presence of unsuspected forces or constraints. Formation of crystal structures should, in theory, resemble what happens to collections of hard spheres when they are compressed on the plane or in space---but this simple mathematical model is not yet fully understood. Finally, scheduling processes (such as computer programs) to avoid conflict is modeled by avoiding collisions in random walks, one of several applications of coordinate percolation. The PI's approach is to use combinatorial methods---rougly speaking, sophisticated means of counting and manipulating discrete objects---to better understand all three models.