- This event has passed.
On a High-Dimensional Random Graph Process
November 6, 2015 @ 11:00 am
Gábor Lugosi (Pompeu Fabra University)
We introduce a model for a high-dimensional random graph process and ask how “rich” the process has to be so that one finds atypical behavior. In particular, we study a natural process of Erdös-Rényi random graphs indexed by unit vectors in R^d . We investigate the deviations of the process with respect to three fundamental properties: clique number, chromatic number, and connectivity. The talk is based on joint work with Louigi Addario-Berry, Shankar Bhamidi, Sebastien Bubeck, Luc Devroye, and Roberto Imbuzeiro Oliveira.