| 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.