Applied Math Colloquium

The percolation model describes the formation of connectivity in random network systems. The scaling theory of percolation will be reviewed and reformulated in a universal form emphasizing the universal fractal nature of this critical phenomenon. Some recent rigorous and conjectured mathematical results that relate to crossing and wrapping probabilities will be summarized, including work by Langlands, Aizenman, Cardy, Duplantier, and Smirnov. Some new numerical observations suggesting an elegant exact result for the number of percolating clusters in strip geometries will be presented. To verify numerically the conjectured formulas for multiple crossing probabilities given by Cardy, Duplantier and Aizenmen, a new rare-event simulation technique (due to Grassberger and Ziff) will be described. Finally, some interesting aspects of percolation on small-world networks --- combination of a random graph and a regular lattice --- will be discussed.

I will present several recent results about geometric folding and unfolding problems. For example, place several rigid rods down on the table, and hinge them together at their ends to form a chain. Is it always possible to fold the hinges in such a way that the linkage is straightened into a line? The rods cannot change in length or cross each other, and must remain on the table. While at first glance it may seem intuitive that any chain can be "unraveled" into a straight line, this "carpenter's rule problem" has proved difficult and remained unsolved for over 25 years.

This problem was solved in a recent burst of interest in folding and unfolding, a branch of discrete and computational geometry. In the past few years, several intriguing and surprising results have been proved about various contexts of folding and unfolding: reconfiguring linkages, paper folding (origami), unfolding polyhedra into nonoverlapping "nets," and gluing polygons into polyhedra. Many of these problems have applications in areas including manufacturing, robotics, and protein folding.

We will discuss some recent developments on random graphs with given expected degree distributions. Such graphs can be used to model various very large graphs arising in Internet and telecommunications and such "massive graphs" in turn shed insight and new directions to random graph theory. For example, it can be shown that the evolution of the sizes of connected components depends primarily on the average degree and the second-order average degree under certain mild conditions. We will also mention a number of problems in random graphs and algorithmic design suggested by various applications of these massive graphs.