McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

DATE: Wednesday, January 21st
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: The evolution of the conductance of a random graph.
SPEAKER: Nikolaos Fountoulakis (McGill University)

The notion of the conductance of a graph was introduced in the context of random walks on graphs for the estimation of the speed of convergence to equilibrium. Also, it has been used in the definition of the notion of an expander graph that has been applied to the design of randomized algorithms. In this talk we estimate the conductance of the giant component of a supercritical random graph, that is a G(n,p) random graph with np>1. We prove that its asymptotic order is min{np/ln n,1}, thus identifying a critical edge probability above which a random graph is with high probability an expander graph. This is joint work with B.A. Reed.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at 
Web Address: