printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 288 - probability seminar

konstantin tikhomirov

princeton university

the spectral gap of dense random regular graphs

abstract:

let $g$ be uniformly distributed on the set of all simple $d$-regular graphs on $n$ vertices, and assume $d$ is bigger than some (small) power of $n$. we show that the second largest eigenvalue of $g$ is of order $\sqrt{d}$ with probability close to one. combined with earlier results covering the case of sparse random graphs, this settles the problem of estimating the magnitude of the second eigenvalue, up to a multiplicative constant, for all values of $n$ and $d$, confirming a conjecture of van vu. joint work with pierre youssef.

host: bruce driver

january 12, 2017

9:00 am

ap&m 6402

****************************