Mathematics Colloquium, Spring 2004
Special Lecture presented by

Graph distance in long-range percolation models

In 1967, using an ingenious sociological experiment, S. Milgram studied the length of acquaintance chains between ``geometrically distant'' individuals. The results led him to the famous conclusion that average two Americans are about six acquaintances (or ``six handshakes'') away from each other. We will model the situation in terms of long-range percolation on~$\mathbb Z^d$, where the nearest neighbor bonds represent the acquaintances due to geometric proximity---people living in the house next door---while long bonds are acquaintances established by other means---e.g., friends form college. The question is: What is the minimal number of bonds one needs to traverse to get from site~$x$ to site~$y$.

Thus, in addition to the usual connections between nearest neighbors on~$\mathbb Z^d$, any two sites~$x,y\in\mathbb Z^d$ at Euclidean distance~$|x-y|$ will be connected by an occupied bond independently with probability proportional to $|x-y|^{-s}$, where~$s>0$ is a parameter. Using $D(x,y)$ to denote the length of the shortest occupied path between~$x$ and~$y$, the main question boils down to the asymptotic scaling of~$D(x,y)$ as $|x-y|\to\infty$. I will discuss a variety of possible behaviors and mention known results and open problems. Then I will sketch the proof of the fact that, when $s\in(d,2d)$, the distance $D(x,y)$ scales like $(\log|x-y|)^\Delta$, where~$\Delta^{-1}$ is the binary logarithm of~$2d/s$.

Tuesday, January 27, 2004, 445 Altgeld Hall, 2:00 p.m.