0README percolation |-- 0README obvious |-- burn.gif 12 summary images from xtoys "xburn" |-- burn-data data from burn.gif: time + extent |-- burn.s R commands: analysis of burn-data |-- burn-output.ps plots generated by analysis `-- perc.s R commands: fill a lattice randomly PERCOLATION Percolation theory and its application is a way to enter into the subject of phase transitions. The fundamental concepts of percolation are perhaps more intuitive than those of the Ising and other models of phase transitions. Yet pecolation displays the central properties of a phase transition: correlation (cooperativity); nonlinearity (explosive growth); emergence of a new structure (infinite connectivity); power law behavior (universality). The percolation model applies variously to: the penetration of a gas into the adsorbant matrix of a gas mask (the early application from which the percoclation model derived its name); the conduction of current across a thin metal film; the properties of partially hydrated protein; the growth of a forest fire (or epidemic); the formation of a galaxy; and much more. Tutorials on percolation theory are to be found on the web. Percolation theory in more than one dimension is mathematically difficult but simple to demonstrate. Two instances are considered here: forest fires; filling a square lattice randomly. FOREST FIRES We model a forest by a square lattice, wrapped edge to opposite edge. Some fraction, p, of the sites are randomly occupied by trees. A fire is started at all filled sites along one edge (along a line with gaps in the wrapped surface). The growth of the fire is simulated in steps. A step corresponds to an interval of time. At each step the fire propagates with unit probability to a neighboring site if it has a tree. Clearly, if only a small fraction of the sites have a tree, the fire will die out quickly, burning only a few trees near the edge, and without burning a large fraction of the tree-ed sites. At high tree density (initial fraction filled large, p ~ 1), the fire will spread quickly and essentially all trees will burn. At some intermediate density, the fire will reach all regions of the forest (the burn will touch all edges of the forest) but the burn is slow. This intermediate density, at which the fire can reach all regions of the forest, is the critical density, p-c, at which there is an infinite cluster of trees. Percolation theory tells us that for a square lattice, p-c = 0.59. The network of trees at p-c is wispy (fractal). Thus the path through it is long and tortuous and the burn is slow. For p < p-c, the burn paths are shorter; also for p > p-c, the burn paths become shorter as the strength of the infinite cluster, P(p), increases. (P(p) = probability a site is part of the infinite cluster; P(p) is the order parameter for the percolation model.) A simulation of the above model, xburn, is one of the original "xtoys" by Mike Creutz of BNL (xburn is not in the current xtoys package). The code and instructions for xburn are in the directory /Users/jar/Sites/Rupley/Code/xtoys. Twelve images from simulations for p=.2-.9 are shown in the file "burn.gif". Each image gives the time for the burn (as the number of iterations) and the number of trees left unburnt. These data (in the file "burn.data") are shown in the two plots of the file "burn-output.ps", for the fraction unburnt and the time of the burn versus the fraction filled, p. The file "burn.s" has the R language commands to generate the plots. Note that as expected from theory, the percolation transition is near p=0.59 and the time of the burn is maximum at the transition. The model for a forest fire applies also to epidemics. For a disease to burn through a population, not only must it be highly contagious, but the density of susceptible individuals must be high. A disease like aids may, as in Western countries, affect a sub-population, but not the entire population. FILLING A SQUARE LATTICE RANDOMLY A Simple Demonstration of Percolation [This is written (and was given) as a student exercise.] [The R language commands in perc.s allow one to generate the set of random numbers and to observe the filling of the lattice on a computer screen.] Carry out a simulation of site percolation on a 10 x 10 square (two-dimensional) lattice. The minimum you need for doing this is a source of random numbers, to generate a list of the order in which the sites are filled. Tables of random numbers are available, and most computers have software for generating a set of acceptably random numbers. You may want to write a small program to generate the list of the order of filling. It is probably easiest to track the behavior of the system by hand, using a 10x10 grid drawn on paper and filling the sites one-by-one, following the previously-generated list of random filling order. Record the point of appearance of the infinite cluster, here defined as a cluster that connects (touches) all *four* edges of the lattice. This defines for your simulation the percolation threshold, p-c, the fraction of sites filled at the appearance of the infinite cluster. Note that for a square lattice, each site has only four neighbors: up, down, left and right. [Diagonal neighbors do not count when determining clusters and paths through the lattice.] Response Requested: (a) Briefly explain how you carried out the simulation. If you wrote a computer program, please submit it. (b) Show your partially filled lattice at p-c. (c) Compare your value of the threshold, p-c, with the literature value, and comment. (d) Turn in a plot of P(p) as a function of the fraction of sites filled. To do this, as you fill each site above the threshold (transition) at p-c, record the number of filled sites that are part of the infinite cluster, as a function of the number of sites filled. From this information, calculate the percolation probability, P(p), as a function of the fraction of sites filled. (NOTE: P(p) is the number of filled sites that are part of the infinite cluster divided by the total number of sites of the lattice (filled and unfilled). P(p) is the order parameter and is also known as the strength of the infinite cluster.) (e) Submit a plot of log (P(p)) vs log (p - p sub c ). (f) Determine the critical exponent, beta, from the above plot. Compare your value with the literature value, beta=.14, and comment. ---------------------------------------------------------------------- ---------------------------------------------------------------------- Class average values(for 11 students): pc = .605 (theory, .59); beta = .180 (theory, .14). The average for pc should be close to theory, as it is. The average for beta is close but not as convincingly. The exponent should be determined from data near pc; this is not possible for a small lattice, owing to the jump character of P(p) for a small lattice (insufficiently smooth to determine slope well near pc). Thus for the class data, the values of beta jump a lot, like the P(p) plot. This problem was assigned because there appeared to be uncertainty among the class as to the nature of a percolation phase transition and the power law behavior of the order parameter. John Rupley rupley@u.arizona.edu -or- jar@rupley.com 30 Calle Belleza, Tucson AZ 85716 - (520) 325-4533; fax - (520) 325-4991 Dept. Biochemistry & Molecular Biophysics, Univ. Arizona, Tucson AZ 85721