Return to Colloquia & Seminar listing

### Graph distance in long-range percolation models

**Special Events**

Speaker: | Marek Biskup, UCLA |

Location: | 693 Kerr |

Start time: | Thu, Feb 5 2004, 4:10PM |

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 Zd, 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 from 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 Zd, any two sites x,y in Zd 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| tends to infinity. 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 the interval (d,2d), the distance D(x,y) scales like (log|x-y|)Delta, where Delta-1 is the binary logarithm of 2d/s.