Next Seminar

Probability theory for THE random graph

Persi Diaconis

Date: 21.10.07

Time: 14:00-14:45 UTC (make sure to keep track of time changes!)


Pick two Erdös-Renyi (n,1/2) graphs uniformly at random. What's the chance they are the same (isomorphic)? Small. How small? Well, at most n!/ 2^(n choose 2). When n= 100, that's less than 10^-1300. OK, now let n=infinity. The chance that the two graphs are isomorphic is one (!). This is THE random graph (the Rado graph R). I will review its many non-random models and many strange properties. — It is a natural limit of the set of all finite graphs (a first order property is true for almost all finite graphs if and only if it holds with probability one in R) and this discontinuity is surprising.

In joint work with with Sourav Chatterjee we tried to find finite manifestations: For finite n, the largest isomorphic induced subgraph of a pair has size 4log (n) -2loglog(n)-2log(4/e) +1 (within 1, all logs base 2 in probability when n is large). This matches data amazingly well (e.g. for n more than 30) and illuminates problems in constraint satisfaction.

A random walk on THE random graph R

Laurent Miclo

Date: 21.10.07

Time: 15:00-15:45 UTC (make sure to keep track of time changes!)


Let q(j) be a probability on N={0,1,2,...}. Let R be a model of THE random graph. A Markov chain on N starts at i and moves to one of its neighbor j in R with probability proportional to q(j). This Markov chain has a stationary distribution and we inquire about rates of convergence. Since each vertex is connected to half of the others and the diameter of R is 2, it seems likely that convergence is fast. In some models we show that log* (i) steps are necessary and sufficient for convergence. The proof uses a novel variant of Hardy's inequalities for trees. This is joint work with Sourav Chatterjee and Persi Diaconis.

Log-in Link

The zoom-link is weekly updated before a seminar session and is given below. If you sign into the mailing list you will receive the link on Wednesdays.


Meeting ID 817 2127 7245

Passcode: 759491

Please turn off your personal videos to reduce the bandwidth used!

If you are having trouble with zoom, or if the capacity of the zoom room gets exceeded, you can also access to the Youtube live stream at the channel of the seminar:


We use zoom, a simple webinar tool. Zoom is not free, but only the hosts (that's us) need a license. All others can log-in via a link. Before the talk you can find the link on this website. Just click on the link and you will be sent to a webinar. There will be a host with control over the microphones.

Please subscribe to our mailing list for updates about the upcoming seminars and other events.