Demetres Christofides: Random Cayley graphs

Lunch is served at 12:00 noon (register at this doodle by Sunday March 9 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

In this talk we will define various models of random Cayley graphs. We will then mention some results and partial results about random Cayley graphs and compare them with the corresponding results for the classical random graphs. We will also recall some of the proofs of the results in the classical case and pinpoint at which places these proofs fail to work in the Cayley case. Finally we will briefly discuss how some of these results in the Cayley case can be obtained.

In the second part of the talk we will concentrate on a specific result for classical random graphs and its corresponding extension for random Cayley graphs: It is known that there is a threshold p(n) such that G(n,p) has diameter greater than 2 if p is slightly below the threshold and diameter equal to 2 if p is slightly above the threshold. In this part of the talk we will discuss how this result extends to random Cayley graphs.